L. Vandenberghe
EE236A (Fall 2013-14)
• a few basic facts • branch-and-bound
Lecture 18
Integer linear programming
18–1
Definitions integer linear program (ILP)
minimize cT x subject to Ax ≤ b
mixed integer linear program: only some of the variables are integer 0-1 (Boolean) linear program: variables take values 0 or 1
Integer linear programming 18–2
x ∈ Zn c
Boolean LP formulation
Example: facility location problem
• n potential facility locations, m clients
• ci: cost of opening a facility at location i • dij: cost of serving client i from location j
minimize subject to
n mn
cjyj + dijxij
variables yj, xij:
yj = 1 location j is selected
xij = 1 xij = 0
location j serves client i otherwise
yj = 0 otherwise Integer linear programming
18–3
j=1 n
i=1 j=1
xij = 1, i = 1,…,m
j=1
xij ≤ yj, i = 1,…,m, j = 1,…,n
xij,yj ∈ {0,1}
Linear programming relaxation relaxation: remove the constraints x ∈ Zn
• provides a lower bound on the optimal value of the integer LP • if solution of relaxation is integer, then it solves the integer LP
cc
equivalent ILP formulations can have different LP relaxations
Integer linear programming 18–4
where P is a finite set general idea
Branch-and-bound algorithm
minimize cT x subject to x ∈ P
• recursively partition P in smaller sets Pi and solve subproblems minimize cT x
subject to x ∈ Pi
• use LP relaxations to discard subproblems that don’t lead to a solution
Integer linear programming 18–5
where
P={x∈Z2+|2×1+1×2≤1, 1×1+1×2≤1} 94 73
x2
−c
Integer linear programming
18–6
Example
minimize −2×1 − 3×2 subject to (x1, x2) ∈ P
optimal point: (2, 2) x1
tree of subproblems and results of LP relaxations
x2 ≤ 2
x2 ≥ 3
x2 ≥ 2
P1
P2
Integer linear programming
18–7
x1 ≤ 2
x1 ≥ 3
P0 (2.17, 2.07) P1 (2.00, 2.14) P2 (3.00, 1.33) P3 (2.00, 2.00) P4 (0.00, 3.00) P5 (3.38, 1.00) P6
−10.56 −10.43 −10.00 −10.00
P0
x⋆ p⋆
x2 ≤ 1
P3 P4 P5 P6
x1 = 3 x1 ≥ 4 P7 P8
P7 (3.00, 1.00) P8 (4.00, 0.44) P9 (4.50, 0.00)
−9.00 −9.75 +∞ −9.00 −9.33 −9.00 +∞ −8.00 +∞
x1 = 4 P11
x1 ≥ 5 P12
P10
P11 (4.00, 0.00)
x2 = 0 x2 = 1 P9 P10
P12
conclusions from relaxed subproblems
• P2: minimizecTxsubjecttox∈P,x1 ≥3
optimal value of subproblem is greater than or equal to −10.00
• P3: minimizecTxsubjecttox∈P,x1 ≤2,×2 ≤2 solution of subproblem is x = (2, 2)
• P6: minimizecTx,subjecttox∈P,x1 ≤3,×2 ≥2 subproblem is infeasible
after solving the relaxations for subproblems
P0, P1, P2, P3, P4
we can conclude that (2, 2) is the optimal solution of the integer LP
Integer linear programming 18–8