Use when formulating mixed integer programming (MIP) models, handling discontinuous variables, modeling logical constraints (either-or, conditional), or linearizing nonlinear terms
Use this skill when you need help with:
This skill provides expert guidance on Integer Linear Programming Tricks based on the AIMMS Modeling Guide. These techniques transform complex, nonlinear, or logical requirements into linear integer programming formulations that can be solved by modern MIP solvers (CPLEX, Gurobi, etc.).
Core Principle: Many practical optimization problems cannot be formulated as pure linear programs because they involve:
These challenges can be addressed using indicator variables (binary 0-1 variables) and Big-M formulations.
Binary indicator variables are the foundation of most MIP tricks. An indicator variable y ∈ {0,1} signals a specific state:
y = 0 → State A
y = 1 → State B
Problem: A variable must be either 0 OR within bounds [l, u]:
x = 0 or l ≤ x ≤ u
Solution: Introduce binary indicator y:
x ≤ uy
x ≥ ly
y binary
When y=0: x=0. When y=1: l ≤ x ≤ u.
Applications:
Problem: Cost function with a jump discontinuity:
C(x) = { 0 if x = 0
{ k + cx if x > 0
where k is the fixed cost and c is the variable cost.
Solution: Introduce binary y and upper bound u:
Minimize: ky + cx
Subject to:
x ≤ uy
x ≥ 0
y binary
When y=0: forces x=0, cost is 0. When y=1: allows x>0, cost is k + cx.
Applications:
Problem: At least one of two constraints must hold:
Constraint (1): Σ a₁ⱼxⱼ ≤ b₁ OR
Constraint (2): Σ a₂ⱼxⱼ ≤ b₂
Solution: Use binary y and Big-M constants M₁, M₂:
Σ a₁ⱼxⱼ ≤ b₁ + M₁y
Σ a₂ⱼxⱼ ≤ b₂ + M₂(1-y)
y binary
When y=0: Constraint (1) is enforced, (2) is relaxed
When y=1: Constraint (2) is enforced, (1) is relaxed
Critical: Choose M values as tight as possible while ensuring they don't restrict feasible solutions.
Applications:
Problem: If constraint (1) holds, then constraint (2) must hold:
If Σ a₁ⱼxⱼ ≤ b₁ then Σ a₂ⱼxⱼ ≤ b₂
Logical Equivalence:
(A → B) ≡ (¬A ∨ B)
This translates to: "Either constraint (1) is violated OR constraint (2) holds"
Solution: Use binary y, Big-M M, lower bound L, and small tolerance ε:
Σ a₁ⱼxⱼ ≥ b₁ + ε - Ly
Σ a₂ⱼxⱼ ≤ b₂ + M(1-y)
y binary
Applications:
Definition: At most ONE variable in the set can be nonzero.
Σᵢ yᵢ ≤ 1 (where yᵢ are 0-1 variables)
More generally, for continuous variables 0 ≤ xᵢ ≤ uᵢ:
Σᵢ aᵢxᵢ ≤ b with at most one xᵢ nonzero
Performance: When variables have a natural ordering, solvers use specialized branching strategies that reduce the search tree.
Example: Warehouse size must be exactly one of: {10000, 20000, 40000, 50000} sq ft.
x₁ + x₂ + x₃ + x₄ = 1 (SOS1)
size = 10000x₁ + 20000x₂ + 40000x₃ + 50000x₄
Definition: At most TWO variables can be nonzero, and they must be adjacent in the ordering.
Used extensively in piecewise linear approximations (see below).
Problem: Approximate a nonlinear function f(x) with a piecewise linear function.
Requirements:
F(x₁, x₂, ...) = f₁(x₁) + f₂(x₂) + ...x₁, x₂, x₃, ..., xₙλ-Formulation:
For breakpoints x₁, x₂, x₃, x₄ with function values f(x₁), f(x₂), f(x₃), f(x₄):
x = λ₁x₁ + λ₂x₂ + λ₃x₃ + λ₄x₄
f̃(x) = λ₁f(x₁) + λ₂f(x₂) + λ₃f(x₃) + λ₄f(x₄)
λ₁ + λ₂ + λ₃ + λ₄ = 1
λᵢ ≥ 0
Plus the adjacency requirement: At most two adjacent λᵢ can be nonzero.
This is exactly a SOS2 constraint.
When Adjacency is Redundant:
In these cases, the LP relaxation automatically satisfies adjacency, and no MIP solve is needed!
When MIP is Required:
Example: Approximate f(x) = ½x² on [0,4] with breakpoints at 0, 1, 2, 4:
Breakpoints: x: 0 1 2 4
Function values: f: 0 0.5 2 8
x = λ₁·0 + λ₂·1 + λ₃·2 + λ₄·4
f̃ = λ₁·0 + λ₂·0.5 + λ₃·2 + λ₄·8
λ₁ + λ₂ + λ₃ + λ₄ = 1 (SOS2)
Problem: Linearize y = x₁x₂ where x₁, x₂ ∈ {0,1}
Solution:
y ≤ x₁
y ≤ x₂
y ≥ x₁ + x₂ - 1
y binary
Problem: Linearize y = x₁x₂ where x₁ ∈ {0,1} and 0 ≤ x₂ ≤ u
Solution:
y ≤ ux₁
y ≤ x₂
y ≥ x₂ - u(1 - x₁)
y ≥ 0
Verification:
x₁=0: constraints force y=0x₁=1: constraints force y=x₂Problem: Linearize x₁x₂ where both are continuous
Solution: Convert to separable form using:
y₁ = ½(x₁ + x₂)
y₂ = ½(x₁ - x₂)
Then: x₁x₂ = y₁² - y₂²
Now approximate y₁² and y₂² using piecewise linear functions.
Special Case: If l₁, l₂ ≥ 0 and x₁ appears ONLY in products, substitute z = x₁x₂ and add:
l₁x₂ ≤ z ≤ u₁x₂
Variable x must satisfy: x = 0 OR l ≤ x ≤ u
Formulation:
x ≤ uy
x ≥ ly
y ∈ {0,1}
Binary y controls whether constraint is active:
y=0: Constraint enforced
y=1: Constraint relaxed
Formulation:
Σ aⱼxⱼ ≤ b + My
For convex minimization or concave maximization:
Just use λ-formulation (adjacency is automatic)
For non-convex:
Mark the convexity constraint as SOS2 property
Binary × Binary: 3 constraints + 1 binary variable
Binary × Continuous: 4 constraints + 1 continuous variable
Continuous × Continuous: Convert to separable, then use piecewise linear
Production Planning
Logistics
Scheduling
Finance
Energy Systems
Choose Big-M Values Carefully
Use SOS When Natural Ordering Exists
Exploit Convexity
Minimize Binary Variables
Preprocessing
Property attribute for SOS1/SOS2 constraintsSee reference files for detailed examples:
references/indicator_variables.md - Binary indicator techniquesreferences/either_or_conditional.md - Logical constraintsreferences/sos_sets.md - Special Ordered Setsreferences/piecewise_linear.md - Nonlinear approximationreferences/product_elimination.md - Linearization techniquesreferences/examples.md - Complete worked examplesBased on Chapter 7 "Integer Linear Programming Tricks" from AIMMS Modeling Guide (AIMMS 4, 1993-2018)
Key sources: