FUNDAMENTALS OF
OPTIMIZATION
Integer Linear Programming
3
CONTENT
• Relaxation and Bound
• Branch and Bound
• Cutting plane
• Gomory Cut
• Branch and Cut
4
RELAXATION AND BOUND
• Given an Integer Program (IP)
• Find decreasing sequence of upper bounds
𝑧ഥ1 > 𝑧ഥ1 > . . . > 𝑧ഥ𝑠 z
• Find increasing sequence of lower bounds
𝑧 1 < 𝑧1 < . . . < 𝑧𝑡 ≤ z
• Algorithm stop when 𝑧ഥ𝑠 - 𝑧𝑡 ≤
5
RELAXATION AND BOUND
• Primal bounds
• Every feasible solution x* X provides a lower bound of the maximization problem: 𝑧 = cx* ≤ z
• Example: in TSP, every closed tour is a upper bound of the objective function (as TSP is a
minimization problem)
6
RELAXATION AND BOUND
• Dual bounds
• Finding upper bounds for a maximization problem (or lower bounds for a minimization problem)
gives dual bounds of the objective
• Definition A problem (RP) zR = max{f(x): xT Rn} is a relaxation of (IP) z = max{cTx: xX Zn} if:
• XT
• f(x) cTx, xX
7
RELAXATION AND BOUND
• Linear Relaxation
• ZLP = max{cTx: x P} with P = {x Rn: Ax ≤ b} is a linear relaxation program of the (IP) max{cTx: x
P Zn}
8
BRANCH AND BOUND
• Feasible region of P0 is divided into feasible regions of P1 and P2: X(P0) = X(P1) X(P2)
𝑧ഥ0
P0
𝑧0
𝑧ഥ01 𝑧ഥ02
P1 P2
𝑧01 𝑧02
9
BRANCH AND BOUND
• Feasible region of P0 is divided into feasible regions of P1 and P2: X(P0) = X(P1) X(P2)
𝑧ഥ0 = 30 𝑧ഥ0 = 20
𝑧0 = 10 𝑧0 = 15
𝑧ഥ01 = 15 𝑧ഥ02 = 20 𝑧ഥ01 = 15 𝑧ഥ02 = 20
𝑧01 = 15 𝑧02 = 13 𝑧01 = 15 𝑧02 = 13
10
BRANCH AND BOUND
• Feasible region of P0 is divided into feasible regions of P1 and P2: X(P0) = X(P1) X(P2)
𝑧ഥ0 = 30 𝑧ഥ0 = 25
𝑧0 = 10 𝑧0 = 23
𝑧ഥ01 = 20 𝑧ഥ02 = 25 𝑧ഥ01 = 20 𝑧ഥ02 = 25
𝑧01 = 15 𝑧02 = 23 𝑧01 = 15 𝑧02 = 23
11
BRANCH AND BOUND
• Branch and Bound schema Initial problem S with formulation P on a list L;
Incumbent x* is initialized with primal bound z = -INF;
while L not empty do {
Select a problem Si with formulation Pi from L;
Solve LP relaxation over Pi got dual bound 𝒛ഥ𝒊 and solution xi(LP);
if 𝒛ഥ𝒊 ≤ z then continue; // prune by dual bound;
if xi(LP) integer then{
z = 𝒛ഥ𝒊 ;
x* = xi(LP);
}else{
select a component xi of xi(LP) whose value i is fractional;
𝑷𝒊𝟏 = Pi (xi ≤ i), 𝑷𝒊𝟐 = Pi (xi i);
add 𝑷𝒊𝟏 and 𝑷𝒊𝟐 to L;
}
}
return x*;
12
CUTTING PLANE
• Given a (MIP) max{cTz: z X}
• Inequality z ≤ 0 is called a valid inequality if z ≤ 0 is true for all z X
• Finding valid inequalities allows us to narrow the search space, transform the (MIP) to a
corresponding (LP) in which an optimal solution to (LP) is an optimal solution to the original (MIP)
13
CUTTING PLANE
• Example, consider a MIP with X = {(x1,x2): x1 ≤ 10x2, 0 ≤ x1 ≤ 14, x2 𝑍+1 }
• Red lines represent X
• x1 ≤ 6 + 4x2 is a valid inequality (dashed line) x2 Feasible points
.
. Valid inequality
.
x1 ≤ 10x2
3
1
x1
0 14
14
CUTTING PLANE
• Example: Integer Rounding
• Consider feasible region X = P Z3 where P = {x𝑅+3 : 5x1 + 9x2 + 13x3 19}
9 13 19
• From 5x1 + 9x2 + 13x3 19 we have x1 + x2 + x
5 5 3 5
19
→ x1 + 2x2 + 3x3
5
• As x1, x2, x3 are integers, so we have
19
x1 + 2x2 + 3x3 = 4 (this is a valid inequality for X)
5
15
GOMORY CUT
• (IP) max {cx: Ax = b, x 0 and integer}
• Solve corresponding linear programming relaxation (LP) max {cx: Ax = b, x 0}
• Suppose with an optimal basis, the (LP) is rewritten in the form
𝑎00 + σ𝑗∈𝐽𝑁 𝑎0𝑗𝑥𝑗 → max
𝑥𝐵𝑢 + σ𝑗∈𝐽𝑁 𝑎𝑢𝑗𝑥𝑗 = 𝑎𝑢0, u = 1, 2,…, m
x 0 and integer
with 𝑎0𝑗 ≤ 0 (as these coefficients corresponds to a maximizer), and 𝑎𝑢0 0
16
GOMORY CUT
• (IP) max {cx: Ax = b, x 0 and integer}
• Solve corresponding linear programming relaxation (LP) max {cx: Ax = b, x 0}
• Suppose with an optimal basis, the (LP) is rewritten in the form
𝑎00 + σ𝑗∈𝐽𝑁 𝑎0𝑗𝑥𝑗 → max
𝑥𝐵𝑢 + σ𝑗∈𝐽𝑁 𝑎𝑢𝑗𝑥𝑗 = 𝑎𝑢0, u = 1, 2,…, m
x 0 and integer
with 𝑎0𝑗 ≤ 0 (as these coefficients corresponds to a maximizer), and 𝑎𝑢0 0
• If the basic optimal solution x* is not integer, then there exists some row u with 𝑎𝑢0 is not integer
→ Create a Gomory cut 𝑥𝐵𝑢 + σ𝑗∈𝐽𝑁 𝑎𝑢𝑗𝑥𝑗 ≤ 𝑎𝑢0 (1)
17
GOMORY CUT
• Example. Consider the Integer Linear Program (ILP)
f(x1, x2, x3, x4, x5) = x1 + x2 → max
2x1 + x2 + x3 = 8
3x1 + 4x2 + x4 = 24
x1 - x2 + x5 = 2
x1, x2, x3, x4, x5 0 and integer
18
GOMORY CUT
• Solve the corresponding (LP)
f(x1, x2, x3, x4, x5) = x1 + x2 → max
2x1 + x2 + x3 = 8
3x1 + 4x2 + x4 = 24
x1 - x2 + x5 = 2
x1, x2, x3, x4, x5 0
→ Optimal solution (1.6, 4.8, 0, 0, 5.2) with JB = (1,2,5) and JN = (3, 4)
Rewrite the original (ILP)
f(x1, x2, x3, x4, x5) = 6.4 – 0.2x3 – 0.2x4 → max
x1 + 0.8x3 – 0.2x4 = 1.6
x2 – 0.6x3 + 0.4 x4 = 4.8
x5 – 1.4x3 + 0.6x4 = 5.2
x1, x2, x3, x4, x5 0 and integer
19
GOMORY CUT
• Add gomory cut
• x1 + 0.8x3 – 0.2x4 = 1.6 → add gomory cut: x1 + 0x3 – x4 ≤ 1
• x2 – 0.6x3 + 0.4 x4 = 4.8 → add gomory cut: x2 – x3 + 0x4 ≤ 4
• x5 – 1.4x3 + 0.6x4 = 5.2 → add gomory cut: x5 – 2x3 + 0x4 ≤ 5
20
THANK YOU !
21
