Decomposition and Dynamic Cut Generation in
Integer Programming
Ted K. Ralphs
Matthew V. Galati
Department of Industrial and Systems Engineering
Lehigh University, Bethlehem, PA
http://www.lehigh.edu/˜tkr2
8th International Workshop on Combinatorial Optimization, January 5-9, 2004, Aussois, France
Decomposition Methods for IP
1
Outline
• Preliminaries, Traditional Decomposition Methods
– Dantzig-Wolfe Decomposition
– Lagrangian Relaxation
– Cutting Plane Method
• Dynamic Decomposition Methods
– Price and Cut
– Relax and Cut
– Decompose and Cut
• Applications/Examples
• DECOMP Framework
Decomposition Methods for IP
2
Preliminaries
• We consider the following pure integer linear program:
zIP = min
x∈F
{c>x} = min
x∈P
{c>x}
where
F = {x ∈ Zn : A′x ≥ b′, A′′x ≥ b′′} Q = {x ∈ Rn : A′x ≥ b′, A′′x ≥ b′′}
F ′= {x ∈ Zn : A′x ≥ b′}
Q′ = {x ∈ Rn : A′x ≥ b′}
Q′′= {x ∈ Rn : A′′x ≥ b′′}
• We will consider P = conv(F) and P ′ = conv(F ′).
• Assumptions
– All input data are rational.
– P is bounded.
– Optimization/separation over P is “difficult.”
– Optimization/separation over P ′ is “easy.”
Decomposition Methods for IP
3
Polyhedra
P = conv({x ∈ Zn : Ax ≥ b})
P ′ = conv({x ∈ Zn : A′x ≥ b′})
P ′
P
Q′ = {x ∈ Rn : A′x ≥ b′}
Q′′ = {x ∈ Rn : A′′x ≥ b′′}
Q′
Q′′
Decomposition Methods for IP
4
Bounding
• Goal: Compute a lower bound on zIP by solving a bounding problem.
• The most commonly used bounding problem is the initial LP relaxation.
min
x∈Q
{c>x}
• Decomposition approaches attempt to improve on this bound by utilizing
implicit knowledge of P ′.
– We have an explicit description of Q′′.
– P ′ is represented implicitly through solution of a subproblem.
• Decomposition methods
– Dantzig-Wolfe decomposition
– Lagrangian relaxation
– Cutting plane method
Decomposition Methods for IP
5
Dantzig-Wolfe Decomposition (DW)
• The bounding problem is the Dantzig-Wolfe LP:
zDW = min{c(
∑
s∈F ′
sλs) : A′′(
∑
s∈F ′
sλs) ≥ b′′,
∑
s∈F ′
λs = 1, λs ≥ 0 ∀s ∈ F ′}
(1)
• Solution method: Simplex algorithm with dynamic column generation.
• Subprob