Mixed Integer Linear Programming

Combinatorial Problem Solving (CPS)

Javier Larrosa Albert Oliveras Enric Rodrı́guez-Carbonell

April 26, 2019

Mixed Integer Linear Programs

■ A mixed integer linear program (MILP, MIP) is of the form

min cT x
Ax = b
x≥0
xi ∈ Z ∀i ∈ I

■ If all variables need to be integer,

it is called a (pure) integer linear program (ILP, IP)

■ If all variables need to be 0 or 1 (binary, boolean),

it is called a 0 − 1 linear program

2 / 46
Complexity: LP vs. IP

■ Including integer variables increases enourmously the modeling power,

at the expense of more complexity

■ LP’s can be solved in polynomial time with interior-point methods

(ellipsoid method, Karmarkar’s algorithm)

■ Integer Programming is an NP-complete problem. So:

◆ There is no known polynomial-time algorithm

◆ There are little chances that one will ever be found

◆ Even small problems may be hard to solve

■ What follows is one of the many approaches

(and one of the most successful) for attacking IP’s

3 / 46
LP Relaxation of a MIP
■ Given a MIP
min cT x
Ax = b
(IP )
x≥0
xi ∈ Z ∀i ∈ I

its linear relaxation is the LP obtained by dropping integrality constraints:

min cT x
(LP ) Ax = b
x≥0

■ Can we solve IP by solving LP ? By rounding?

4 / 46
Branch & Bound

■ The optimal solution of

max x + y
−2x + 2y ≥ 1
−8x + 10y ≤ 13
x, y ≥ 0
x, y ∈ Z

is (x, y) = (1, 2), with objective 3

■ The optimal solution of its LP relaxation

is (x, y) = (4, 4.5), with objective 9.5

■ No direct way of getting from (4, 4.5) to (1, 2) by rounding!

■ Something more elaborate is needed: branch & bound

5 / 46
Branch & Bound

(4, 4.5)
−8x + 10y ≤ 13

(1, 2) max x + y
x≥0 −2x + 2y ≥ 1
(0, 1)

y≥0 x

6 / 46
Branch & Bound
■ Assume variables are bounded, i.e., have lower and upper bounds
■ Let P0 be the initial problem, LP(P0 ) be the LP relaxation of P0
■ If in optimal solution of LP(P0 ) all integer variables take integer values
then it is also an optimal solution to P0
■ Else
◆ Let xj be integer variable
whose value βj at optimal solution of LP(P0 ) is such that βj 6∈ Z.
Define
P1 := P0 ∧ xj ≤ ⌊βj ⌋
P2 := P0 ∧ xj ≥ ⌈βj ⌉

◆ feasibleSols(P0 ) = feasibleSols(P1 ) ∪ feasibleSols(P2 )

◆ Idea: solve P1 , solve P2 and then take the best

7 / 46
Branch & Bound
■ Let xj be integer variable
whose value βj at optimal solution of LP(P0 ) is such that βj 6∈ Z.
Each of the problems

P1 := P0 ∧ xj ≤ ⌊βj ⌋ P2 := P0 ∧ xj ≥ ⌈βj ⌉

can be solved recursively

■ We can build a binary tree of subproblems
whose leaves correspond to pending problems still to be solved
■ This procedure terminates as integer vars have finite bounds and,
at each split, the range of xj becomes strictly smaller
■ If LP(Pi ) has optimal solution where integer variables take integer values
then solution is stored
■ If LP(Pi ) is infeasible then Pi can be discarded (pruned, fathomed)

8 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
End
====================================================================

CPLEX> optimize
Primal simplex - Optimal: Objective = - 8.5000000000e+00
Solution time = 0.00 sec. Iterations = 0 (0)
Deterministic time = 0.00 ticks (0.37 ticks/sec)

CPLEX> display solution variables x

Variable Name Solution Value
x 4.000000

CPLEX> display solution variables y

Variable Name Solution Value
y 4.500000

9 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
y >= 5
End
====================================================================

CPLEX> optimize
Bound infeasibility column ’x’.
Presolve time = 0.00 sec. (0.00 ticks)
Presolve - Infeasible.
Solution time = 0.00 sec.
Deterministic time = 0.00 ticks (1.67 ticks/sec)

10 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
y <= 4
End
====================================================================

CPLEX> optimize
Dual simplex - Optimal: Objective = - 7.5000000000e+00
Solution time = 0.00 sec. Iterations = 0 (0)
Deterministic time = 0.00 ticks (2.68 ticks/sec)

CPLEX> display solution variables x

Variable Name Solution Value
x 3.500000

CPLEX> display solution variables y

Variable Name Solution Value
y 4.000000

11 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x >= 4
y <= 4
End
====================================================================

CPLEX> optimize
Row ’c1’ infeasible, all entries at implied bounds.
Presolve time = 0.00 sec. (0.00 ticks)
Presolve - Infeasible.
Solution time = 0.00 sec.
Deterministic time = 0.00 ticks (1.11 ticks/sec)

12 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x <= 3
y <= 4
End
====================================================================

CPLEX> optimize
Dual simplex - Optimal: Objective = - 6.7000000000e+00
Solution time = 0.00 sec. Iterations = 0 (0)
Deterministic time = 0.00 ticks (2.71 ticks/sec)

CPLEX> display solution variables x

Variable Name Solution Value
x 3.000000

CPLEX> display solution variables y

Variable Name Solution Value
y 3.700000
13 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x <= 3
y = 4
End
====================================================================

CPLEX> optimize
Bound infeasibility column ’x’.
Presolve time = 0.00 sec. (0.00 ticks)
Presolve - Infeasible.
Solution time = 0.00 sec.
Deterministic time = 0.00 ticks (1.12 ticks/sec)

14 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x <= 3
y <= 3
End
====================================================================

CPLEX> optimize
Dual simplex - Optimal: Objective = - 5.5000000000e+00
Solution time = 0.00 sec. Iterations = 0 (0)
Deterministic time = 0.00 ticks (2.71 ticks/sec)

CPLEX> display solution variables x

Variable Name Solution Value
x 2.500000

CPLEX> display solution variables y

Variable Name Solution Value
y 3.000000
15 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x = 3
y <= 3
End
====================================================================

CPLEX> optimize
Bound infeasibility column ’y’.
Presolve time = 0.00 sec. (0.00 ticks)
Presolve - Infeasible.
Solution time = 0.00 sec.
Deterministic time = 0.00 ticks (1.11 ticks/sec)

16 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x <= 2
y <= 3
End
====================================================================

CPLEX> optimize
Dual simplex - Optimal: Objective = - 4.9000000000e+00
Solution time = 0.00 sec. Iterations = 0 (0)
Deterministic time = 0.00 ticks (2.71 ticks/sec)

CPLEX> display solution variables x

Variable Name Solution Value
x 2.000000
CPLEX> display solution variables y
Variable Name Solution Value
y 2.900000

17 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x <= 2
y = 3
End
====================================================================

CPLEX> optimize
Bound infeasibility column ’x’.
Presolve time = 0.00 sec. (0.00 ticks)
Presolve - Infeasible.
Solution time = 0.00 sec.
Deterministic time = 0.00 ticks (1.12 ticks/sec)

18 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x <= 2
y <= 2
End
====================================================================

CPLEX> optimize
Dual simplex - Optimal: Objective = - 3.5000000000e+00
Solution time = 0.00 sec. Iterations = 0 (0)
Deterministic time = 0.00 ticks (2.71 ticks/sec)

CPLEX> display solution variables x

Variable Name Solution Value
x 1.500000

CPLEX> display solution variables y

Variable Name Solution Value
y 2.000000
19 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x = 2
y <= 2
End
====================================================================

CPLEX> optimize
Bound infeasibility column ’y’.
Presolve time = 0.00 sec. (0.00 ticks)
Presolve - Infeasible.
Solution time = 0.00 sec.
Deterministic time = 0.00 ticks (1.11 ticks/sec)

20 / 46
Example
Min obj: - x - y
Subject To
c1: -2 x + 2 y >= 1
c2: -8 x + 10 y <= 13
Bounds
x <= 1
y <= 2
End
====================================================================

CPLEX> optimize
Dual simplex - Optimal: Objective = - 3.0000000000e+00
Solution time = 0.00 sec. Iterations = 0 (0)
Deterministic time = 0.00 ticks (2.40 ticks/sec)

CPLEX> display solution variables x

Variable Name Solution Value
x 1.000000

CPLEX> display solution variables y

Variable Name Solution Value
y 2.000000
21 / 46
Pruning in Branch & Bound
■ We have already seen that if relaxation is infeasible,
the problem can be pruned

■ Now assume an (integral) solution has been previously found

■ If solution has cost Z then any pending problem Pj whose relaxation has
optimal value ≥ Z can be ignored, since

cost(Pj ) ≥ cost(LP(Pj )) ≥ Z

The optimum will not be in any descendant of Pj !

■ This cost-based pruning of the search tree has a huge impact

on the efficiency of Branch & Bound

22 / 46
Branch & Bound: Algorithm

S := {P0 } /* set of pending problems */

Z := +∞ /* best cost found so far */
while S 6= ∅ do
remove P from S
solve LP(P )
if LP(P ) is feasible then /* if unfeasible P can be pruned */
let β be optimal basic solution of LP(P )
if β satisfies integrality constraints then
if cost(β) < Z then store β; update Z
else
if cost(LP(P )) ≥ Z then continue /* P can be pruned */
let xj be integer variable such that βj 6∈ Z
S := S ∪ { P ∧ xj ≤ ⌊βj ⌋, P ∧ xj ≥ ⌈βj ⌉ }
return Z

23 / 46
Heuristics in Branch & Bound
■ Possible choices in Branch & Bound

◆ Choice of the pending problem

■ Depth-first search
■ Breadth-first search
■ Best-first search: assuming relaxations are solved when adding to
the set of pending problems, select the one with best cost value

24 / 46
Heuristics in Branch & Bound
■ Possible choices in Branch & Bound

◆ Choice of the pending problem

■ Depth-first search
■ Breadth-first search
■ Best-first search: assuming relaxations are solved when adding to
the set of pending problems, select the one with best cost value

◆ Choice of the branching variable: one that is

■ closest to halfway two integer values

■ most important in the model (e.g., 0-1 variable)
■ biggest in a variable ordering
■ the one with the largest/smallest cost coefficient

24 / 46
Heuristics in Branch & Bound
■ Possible choices in Branch & Bound

◆ Choice of the pending problem

■ Depth-first search
■ Breadth-first search
■ Best-first search: assuming relaxations are solved when adding to
the set of pending problems, select the one with best cost value

◆ Choice of the branching variable: one that is

■ closest to halfway two integer values

■ most important in the model (e.g., 0-1 variable)
■ biggest in a variable ordering
■ the one with the largest/smallest cost coefficient

■ No known strategy is best for all problems!

24 / 46
Remarks on Branch & Bound

■ If integer variables are not bounded, Branch & Bound may not terminate:
min 0
1 ≤ 3x − 3y ≤ 2
x, y ∈ Z
is infeasible but Branch & Bound loops forever looking for solutions!

25 / 46
Remarks on Branch & Bound

■ If integer variables are not bounded, Branch & Bound may not terminate:
min 0
1 ≤ 3x − 3y ≤ 2
x, y ∈ Z
is infeasible but Branch & Bound loops forever looking for solutions!

■ After solving the relaxation of P ,

we have to solve the relaxations of P ∧ xj ≤ ⌊βj ⌋ and P ∧ xj ≥ ⌈βj ⌉

■ These problems are similar. Do we have to start from scratch?

Can be reuse somehow the computation for P ?

■ Idea: start from the optimal solution of the parent problem

25 / 46
Remarks on Branch & Bound
■ Let us assume that P is of the form
min cT x
Ax = b
x ≥ 0, xi ∈ Z ∀i ∈ I

■ Let B be an optimal basis of the relaxation

■ Let xj be integer variable which at optimal solution is assigned βj 6∈ Z

■ Note that xj must be basic

■ Let us consider the problem P1 = P ∧ xj ≤ ⌊βj ⌋

■ We add a new slack variable s and a new equation P ∧ xj + s = ⌊βj ⌋

■ Then (xB , s) defines a basis for the relaxation of P1

26 / 46
Remarks on Branch & Bound
■ (xB , s) defines a basis for the relaxation of P1

■ This basis is not feasible:

the value in the basic solution assigned to s is ⌊βj ⌋ − βj < 0.
We would need a Phase I to apply the primal simplex method!

■ But since s is a slack the reduced costs have not changed:

(xB , s) satisfies the optimality conditions!

■ Dual simplex method can be used:

basis (xB , s) is already dual feasible, no need of (dual) Phase I

■ In practice often the dual simplex only needs very few iterations
to obtain the optimal solution to the new problem

27 / 46
Cutting Planes
■ Let us consider a MIP of the form
  
 Ax = b
min cT x
  
where S = x ∈ Rn  x≥0
x∈S  
 xi ∈ Z ∀i ∈ I 

and its linear relaxation


cT x
 
min  Ax = b

where P = x ∈ Rn 
x∈P   x≥0

■ Let β be such that β ∈ P but β 6∈ S.

A cut for β is a linear inequality âT x ≤ b̂ such that
◆ âT σ ≤ b̂ for any σ ∈ S (feasible solutions of the MIP respect the cut)
◆ and âT β > b̂ (β does not respect the cut)

28 / 46
Cutting Planes

max x + y

y max x + y
−2x + 2y ≥ 1
(4, 4.5) −8x + 10y ≤ 13
x, y ≥ 0
−8x + 10y ≤ 13 x, y ∈ Z

(1, 2)

(0, 1) −2x + 2y ≥ 1 x + y ≤ 6 is a cut

x≥0 x+y ≤6
y≥0 x

29 / 46
Using Cuts for Solving MIP’s
■ Let âT x ≤ b̂ be a cut. Then the MIP
 
  Ax = b 
min cT x
 
âT x ≤ b̂
  
where S ′ = x ∈ Rn 
x ∈ S′  
 x≥0 

xi ∈ Z ∀i ∈ I
 

has the same set of feasible solutions S

but its LP relaxation is strictly more constrained

■ Instead of splitting into subproblems (Branch & Bound),

one can add the cut and solve the relaxation of the new problem

■ In practice cuts are used together with Branch & Bound:

If after adding some cuts no integer solution is found, then branch
This technique is called Branch & Cut

30 / 46
Gomory Cuts
■ There are several techniques for deriving cuts
■ Some are problem-specific (e.g., for the travelling salesman problem)
■ Here we will see a generic technique: Gomory cuts
■ Let us consider a basis B and let β be the associated basic solution.
Note that for all j ∈ R we have βj = 0

■ Let xi be a basic variable such that i ∈ I and βi 6∈ Z

■ E.g., this happens in the optimal basis of the relaxation
when the basic solution does not meet the integrality constraints
■ Let the row of the tableau corresponding to xi be of the form
P
xi = β i + j∈R αij xj

31 / 46
Gomory Cuts
■ Let x ∈ S. Then xi ∈ Z and
P
xi = β i + j∈R αij xj
P
xi − β i = j∈R αij xj

■ Let δ = βi − ⌊βi ⌋. Then 0 < δ < 1

■ Hence
xi − ⌊βi ⌋ = xi − βi + βi − ⌊βi ⌋
= xi − β i + δ
= δ + xi − β i
P
= δ + j∈R αij xj

32 / 46
Gomory Cuts
P
xi − ⌊βi ⌋ = δ + j∈R αij xj

■ Let us define
R+ = {j ∈ R | αij ≥ 0} R− = {j ∈ R | αij < 0}

33 / 46
Gomory Cuts
P
xi − ⌊βi ⌋ = δ + j∈R αij xj

■ Let us define
R+ = {j ∈ R | αij ≥ 0} R− = {j ∈ R | αij < 0}
P
■ Assume j∈R αij xj ≥ 0. Then
X
δ+ αij xj ≥ 1
j∈R
X X
αij xj ≥ αij xj ≥ 1 − δ
j∈R+ j∈R
X αij
xj ≥ 1
1−δ
j∈R+

33 / 46
Gomory Cuts
P
xi − ⌊βi ⌋ = δ + j∈R αij xj

■ Let us define
R+ = {j ∈ R | αij ≥ 0} R− = {j ∈ R | αij < 0}
P
■ Assume j∈R αij xj ≥ 0. Then
X
δ+ αij xj ≥ 1
j∈R
X X
αij xj ≥ αij xj ≥ 1 − δ
j∈R+ j∈R
X αij
xj ≥ 1
1−δ
j∈R+
 
P −αij
Moreover j∈R− δ xj ≥ 0

33 / 46
Gomory Cuts
P
xi − ⌊βi ⌋ = δ + j∈R αij xj

■ Let us define
R+ = {j ∈ R | αij ≥ 0} R− = {j ∈ R | αij < 0}

34 / 46
Gomory Cuts
P
xi − ⌊βi ⌋ = δ + j∈R αij xj

■ Let us define
R+ = {j ∈ R | αij ≥ 0} R− = {j ∈ R | αij < 0}
P
■ Assume j∈R αij xj < 0. Then
X
δ+ αij xj ≤ 0
j∈R
X X
αij xj ≤ αij xj ≤ −δ
j∈R− j∈R
X  −αij 
xj ≥ 1
δ
j∈R−

34 / 46
Gomory Cuts
P
xi − ⌊βi ⌋ = δ + j∈R αij xj

■ Let us define
R+ = {j ∈ R | αij ≥ 0} R− = {j ∈ R | αij < 0}
P
■ Assume j∈R αij xj < 0. Then
X
δ+ αij xj ≤ 0
j∈R
X X
αij xj ≤ αij xj ≤ −δ
j∈R− j∈R
X  −αij 
xj ≥ 1
δ
j∈R
−

P αij
Moreover j∈R+ 1−δ xj ≥0

34 / 46
Gomory Cuts
In any case
X  −αij  X αij
xj + xj ≥ 1
δ +
1−δ
j∈R
− j∈R

for any x ∈ S.

However, when x = β this inequality is not satisfied (set xj = 0 for j ∈ R)

35 / 46
Ensuring All Vertices Are Integer
■ Let us assume A, b have coefficients in Z
■ Sometimes it is possible to ensure for an IP that
all vertices of the relaxation are integer
■ For instance, when the matrix A is totally unimodular:
the determinant of every square submatrix is 0 or ±1

36 / 46
Ensuring All Vertices Are Integer
■ Let us assume A, b have coefficients in Z
■ Sometimes it is possible to ensure for an IP that
all vertices of the relaxation are integer
■ For instance, when the matrix A is totally unimodular:
the determinant of every square submatrix is 0 or ±1
In that case all bases have inverses with integer coefficients
Recall Cramer’s rule: if B is an invertible matrix, then

−1 1
B = adj(B)
det(B)
where adj(B) is the adjugate matrix of B
Recall also that

adj(B) = ((−1)i+j det(Mji ))1≤i,j≤n ,

where Mij is matrix B after removing the i-th row and the j-th column
36 / 46
Ensuring All Vertices Are Integer
■ Sufficient condition for total unimodularity of a matrix A:
(Hoffman & Gale’s Theorem)

1. Each element of A is 0 or ±1
2. No more than two non-zeros appear in each columm
3. Rows can be partitioned in two subsets R1 and R2 s.t.

(a) If a column contains two non-zeros of the same sign,

one element is in each of the subsets
(b) If a column contains two non-zeros of different signs,
both elements belong to the same subset

37 / 46
Assignment Problem
■ n = # of workers = # of tasks
■ Each worker must be assigned to exactly one task
■ Each task is to be performed by exactly one worker
■ cij = cost when worker i performs task j

38 / 46
Assignment Problem
■ n = # of workers = # of tasks
■ Each worker must be assigned to exactly one task
■ Each task is to be performed by exactly one worker
■ cij = cost when worker i performs task j


1 if worker i performs task j
xij =
0 otherwise

Pn Pn
min i=1 j=1 cij xij
Pn
j=1 xij =1 ∀i ∈ {1, . . . , n}
Pn
i=1 xij =1 ∀j ∈ {1, . . . , n}
xij ∈ {0, 1} ∀i, j ∈ {1, . . . , n}

■ This problem satisfies Hoffman & Gale’s conditions

38 / 46
Ensuring All Vertices Are Integer
■ Several kinds of IP’s satisfy Hoffman & Gale’s conditions:

◆ Assignment
◆ Transportation
◆ Maximum flow
◆ Shortest path
◆ ...

■ Usually ad-hoc network algorithms are more efficient for these problems
than the simplex method as presented here

39 / 46
Ensuring All Vertices Are Integer
■ Several kinds of IP’s satisfy Hoffman & Gale’s conditions:

◆ Assignment
◆ Transportation
◆ Maximum flow
◆ Shortest path
◆ ...

■ Usually ad-hoc network algorithms are more efficient for these problems
than the simplex method as presented here
■ But:
◆ The simplex method can be specialized: network simplex method
◆ Simplex techniques can be applied
if the problem is not a purely network one but has extra constraints

39 / 46
Expressing Logical Constraints
■ Sometimes we want to have an indicator variable of a contraint:
a 0/1 variable equal to 1 iff the constraint is true (= reification in CP)

■ E.g., let us to encode δ = 1 ↔ aT x ≤ b, where δ is a 0/1 var

40 / 46
Expressing Logical Constraints
■ Sometimes we want to have an indicator variable of a contraint:
a 0/1 variable equal to 1 iff the constraint is true (= reification in CP)

■ E.g., let us to encode δ = 1 ↔ aT x ≤ b, where δ is a 0/1 var

■ Assume aT x ∈ Z for all feasible solution x

Let U be an upper bound of aT x − b for all feasible solutions
Let L be a lower bound of aT x − b for all feasible solutions

40 / 46
Expressing Logical Constraints
■ Sometimes we want to have an indicator variable of a contraint:
a 0/1 variable equal to 1 iff the constraint is true (= reification in CP)

■ E.g., let us to encode δ = 1 ↔ aT x ≤ b, where δ is a 0/1 var

■ Assume aT x ∈ Z for all feasible solution x

Let U be an upper bound of aT x − b for all feasible solutions
Let L be a lower bound of aT x − b for all feasible solutions

1. δ = 1 → aT x ≤ b
can be encoded with aT x − b ≤ U (1 − δ)

40 / 46
Expressing Logical Constraints
■ Sometimes we want to have an indicator variable of a contraint:
a 0/1 variable equal to 1 iff the constraint is true (= reification in CP)

■ E.g., let us to encode δ = 1 ↔ aT x ≤ b, where δ is a 0/1 var

■ Assume aT x ∈ Z for all feasible solution x

Let U be an upper bound of aT x − b for all feasible solutions
Let L be a lower bound of aT x − b for all feasible solutions

1. δ = 1 → aT x ≤ b
can be encoded with aT x − b ≤ U (1 − δ)

2. δ = 1 ← aT x ≤ b
δ = 0 → aT x > b
δ = 0 → aT x ≥ b + 1
can be encoded with aT x − b ≥ (L − 1)δ + 1
40 / 46
Expressing Logical Constraints
■ We want to encode δ = 1 ↔ aT x ≤ b, where δ is a 0/1 var

■ Now assume that aT x is real-valued.

Let U be an upper bound of aT x − b for all feasible solutions
Let L be a lower bound of aT x − b for all feasible solutions

1. δ = 1 → aT x ≤ b
can be encoded with aT x − b ≤ U (1 − δ)

41 / 46
Expressing Logical Constraints
■ We want to encode δ = 1 ↔ aT x ≤ b, where δ is a 0/1 var

■ Now assume that aT x is real-valued.

Let U be an upper bound of aT x − b for all feasible solutions
Let L be a lower bound of aT x − b for all feasible solutions

1. δ = 1 → aT x ≤ b
can be encoded with aT x − b ≤ U (1 − δ)

2. δ = 1 ← aT x ≤ b
δ = 0 → aT x > b Can only be modeled if we allow for a tolerance ǫ

41 / 46
Expressing Logical Constraints
■ We want to encode δ = 1 ↔ aT x ≤ b, where δ is a 0/1 var

■ Now assume that aT x is real-valued.

Let U be an upper bound of aT x − b for all feasible solutions
Let L be a lower bound of aT x − b for all feasible solutions

1. δ = 1 → aT x ≤ b
can be encoded with aT x − b ≤ U (1 − δ)

2. δ = 1 ← aT x ≤ b
δ = 0 → aT x > b Can only be modeled if we allow for a tolerance ǫ
δ = 0 → aT x ≥ b + ǫ
can be encoded with aT x − b ≥ (L − ǫ)δ + ǫ

41 / 46
Expressing Logical Constraints
■ We want to encode δ = 1 ↔ aT x = b, where δ is a 0/1 var
■ Assume that aT x is real-valued.
Let U be upper bound of aT x − b for all feasible solutions
Let L be lower bound of aT x − b for all feasible solutions

42 / 46
Expressing Logical Constraints
■ We want to encode δ = 1 ↔ aT x = b, where δ is a 0/1 var
■ Assume that aT x is real-valued.
Let U be upper bound of aT x − b for all feasible solutions
Let L be lower bound of aT x − b for all feasible solutions

1. δ = 1 → aT x ≤ b ⇒ aT x − b ≤ U (1 − δ)

42 / 46
Expressing Logical Constraints
■ We want to encode δ = 1 ↔ aT x = b, where δ is a 0/1 var
■ Assume that aT x is real-valued.
Let U be upper bound of aT x − b for all feasible solutions
Let L be lower bound of aT x − b for all feasible solutions

1. δ = 1 → aT x ≤ b ⇒ aT x − b ≤ U (1 − δ)
2. δ = 1 → aT x ≥ b ⇒ aT x − b ≥ L(1 − δ)

42 / 46
Expressing Logical Constraints
■ We want to encode δ = 1 ↔ aT x = b, where δ is a 0/1 var
■ Assume that aT x is real-valued.
Let U be upper bound of aT x − b for all feasible solutions
Let L be lower bound of aT x − b for all feasible solutions

1. δ = 1 → aT x ≤ b ⇒ aT x − b ≤ U (1 − δ)
2. δ = 1 → aT x ≥ b ⇒ aT x − b ≥ L(1 − δ)
3. δ = 1 ← aT x = b
δ = 0 → aT x 6= b
δ = 0 → aT x < b ∨ aT x > b

42 / 46
Expressing Logical Constraints
■ We want to encode δ = 1 ↔ aT x = b, where δ is a 0/1 var
■ Assume that aT x is real-valued.
Let U be upper bound of aT x − b for all feasible solutions
Let L be lower bound of aT x − b for all feasible solutions

1. δ = 1 → aT x ≤ b ⇒ aT x − b ≤ U (1 − δ)
2. δ = 1 → aT x ≥ b ⇒ aT x − b ≥ L(1 − δ)
3. δ = 1 ← aT x = b
δ = 0 → aT x 6= b
δ = 0 → aT x < b ∨ aT x > b
Let ǫ be the tolerance, δ ′ , δ ′′ auxiliary 0/1 vars
δ = 0 → δ ′ = 0 ∨ δ ′′ = 0 ⇒ δ ′ + δ ′′ − δ ≤ 1
δ ′ = 0 → aT x ≤ b − ǫ ⇒ aT x − b ≤ (U + ǫ)δ ′ − ǫ
δ ′′ = 0 → aT x ≥ b + ǫ ⇒ aT x − b ≥ (L − ǫ)δ ′′ + ǫ
42 / 46
Expressing Logical Constraints

■ Boolean expressions can be modeled with 0/1 vars

■ If xi is a 0/1 variable,
let Xi be a boolean variable such that Xi is true iff xi = 1

X1 ∨ X2 iff x1 + x2 ≥ 1
X1 ∧ X2 iff x1 = x2 = 1
¬X1 iff x1 = 0
X1 → X2 iff x1 ≤ x2
X1 ↔ X2 iff x1 = x2

43 / 46
Example
Let Xi represent “Ingredient i is in the blend”, i ∈ {A, B, C}.
Express the sentence

“If ingredient A is in the blend,

then ingredient B or C (or both) must also be in the blend”

with linear constraints.

44 / 46
Example
Let Xi represent “Ingredient i is in the blend”, i ∈ {A, B, C}.
Express the sentence

“If ingredient A is in the blend,

then ingredient B or C (or both) must also be in the blend”

with linear constraints.

■ We need to express XA → (XB ∨ XC ).

■ Equivalently, ¬XA ∨ XB ∨ XC .

■ ¬XA ∨ XB ∨ XC is equivalent to (1 − xA ) + xB + xC ≥ 1.

■ So xB + xC ≥ xA

44 / 46
Example (Fixed Setup Charge)
Let x be the quantity of a product with unit production cost c1 .
If the product is manufactured at all, there is a setup cost c0


0 if x = 0
Cost of producing x units =
c0 + c1 x if x > 0

Want to minimize costs. Model as a MIP?

(for simplicity, additional constraints are not specified and can be omitted)

45 / 46
Example (Fixed Setup Charge)
Let x be the quantity of a product with unit production cost c1 .
If the product is manufactured at all, there is a setup cost c0


0 if x = 0
Cost of producing x units =
c0 + c1 x if x > 0

Want to minimize costs. Model as a MIP?

(for simplicity, additional constraints are not specified and can be omitted)

Let δ be 0/1 var such that x > 0 → δ = 1 (i.e., δ = 0 → x ≤ 0):

add constraint x − U δ ≤ 0, where U is the upper bound on x

Then the cost is c0 δ + c1 x.

No need to express x > 0 ← δ = 1, i.e. x = 0 → δ = 0

Minimization will make δ = 0 if possible (i.e., if x = 0)

45 / 46
Example (Capacity Expansion)
Let aT x be the consumption of a limited resource in a production process
Want to relax the constraint aT x ≤ b by increasing capacity b.
Capacity can be expanded to bi

b = b 0 < b1 < b2 < · · · < b t

with costs, respectively,

0 = c0 < c1 < c2 < · · · < ct

Want to minimize costs. Model as a MIP?

(for simplicity, additional constraints are not specified and can be omitted)

46 / 46
Example (Capacity Expansion)
Let aT x be the consumption of a limited resource in a production process
Want to relax the constraint aT x ≤ b by increasing capacity b.
Capacity can be expanded to bi

b = b 0 < b1 < b2 < · · · < b t

with costs, respectively,

0 = c0 < c1 < c2 < · · · < ct

Want to minimize costs. Model as a MIP?

(for simplicity, additional constraints are not specified and can be omitted)
Let 0/1 variables δi mean “capacity expanded to bi ”. Then:
Pt
■ i=0 δi = 1
T
Pt
■ a x≤ i=0 bi δi
Pt
■ Cost function: i=0 ci δi
46 / 46