Integer Programming Formulations and Tricks¶
Integer Programming (IP) is a powerful optimization technique used when decision variables must take integer or binary values. It’s widely applied in scheduling, resource allocation, and supply chain optimization.
In this blog, we explore tricks to convert non-linear or logical constraints into linear\integer-based formulations. These techniques allow us to model complex decision-making problems as integer programming problems and solve them efficiently using standard solvers.
Binary Variables¶
Binary variables take values in {0,1} and are used to represent yes/no decisions.
Example: If a machine is used → y = 1, else y = 0.
Big-M Method¶
Big-M is a large positive constant used to relax constraints when a condition is not enforced.
- Choose M as small as possible for computational efficiency.
- Avoid excessively large M to prevent numerical instability.
IF-THEN Constraint¶
Used to model precedence or conditional activation.
If \(x = 1\) then \(y = 1\):
$$ x \leq y $$
If \(x = 1\) then \(y ≠ 1\):
$$ x \leq 1 - y $$
If \(x = 0\) then \(y = 0\):
$$ x \geq y $$
Example: Enroll in class x before class y.
Logical OR Constraint¶
Ensures at least one condition holds.
At least one of x or y is true:
$$ x + y \geq 1 $$ Exclusive OR (XOR):
$$ x + y = 1 $$ z is true if x or y is true:
$$ x \leq z,\; y \leq z,\; z \leq x + y $$ Example: Choose at least one of two projects.
Logical AND Constraint¶
Ensures both conditions hold.
Both x and y must be true:
$$ x + y \geq 2 $$ z is true only if both x and y are true:
$$ z \leq x,\; z \leq y,\; z \geq x + y - 1 $$ Example: Activate a system only if both modules are online.
Discontinuous Variables¶
Used to model fixed cost decisions.
x is either zero or in range [l, u]:
$$ x \leq u y,\; x \geq l y,\; y \in {0,1} $$ z = 1 when x > 0:
$$ x \leq M y $$ Example: Production incurs fixed cost only if quantity > 0.
Either-Or Constraints¶
Used to model disjunctive constraints.
Either \(ax \leq b\) or \(cx \leq d\):
$$ ax \leq b + M y,\; cx \leq d + M(1 - y) $$ Example: Choose one of two manufacturing methods.
Conditional Constraints¶
Used to enforce one constraint based on another.
If \(a_1\times x \geq b_1\) then \(a_2\times x \leq b_2\):
$$ a_1\times x \geq b_1 - M y,\; a_2\times x \leq b_2 + M(1 - y) $$ If \(a_1\times x \leq b_1\) then \(a_2\times x \leq b_2\):
$$ a_1\times x \leq b_1 + M y,\; a_2\times x \leq b_2 + M(1 - y) $$ Example: Blending problem where one ingredient triggers another constraint.
Piecewise Linear Approximation¶
Used to approximate non-linear functions. Divide domain into intervals and use binary variables to activate segments.
Example: Useful for modeling cost functions like \( y = x^2 \). 
Summary¶
- Use binary variables for logical decisions.
- Apply Big-M carefully.
- Model complex conditions using IF-THEN, OR, AND, Either-Or, and Conditional constraints.
- Use piecewise linearization for non-linear objectives.