Column Generation method in linear programming

Column Generation method in linear programming

1. Column
Generation
Jacques Desrosiers
Ecole des HEC & GERAD

2. COLUMN GENERATION 2
Contents
• The Cutting Stock Problem
 Basic Observations
 LP Column Generation
 Dantzig-Wolfe Decomposition
 Dantzig-Wolfe decomposition
vs Lagrangian Relaxation
 Equivalencies
 Alternative Formulations to
the Cutting Stock Problem
 IP Column Generation
 Branch-and- ...
 Acceleration Techniques
 Concluding Remarks

3. COLUMN GENERATION 3
A Classical Paper :
The Cutting Stock Problem
P.C. Gilmore & R.E.
Gomory
A Linear Programming
Approach to the Cutting
Stock Problem.
Oper. Res. 9, 849-859.
(1960)
: set of items
: number of times
item i is requested
: length of item i
: length of a standard roll
: set of cutting patterns
: number of times item i is
cut in pattern j
: number of times
pattern j is used
ij
a
il
j
Y
i
n
I
J
L

4. COLUMN GENERATION 4
The Cutting Stock
Problem ...
Set can be huge.
Solution of
the linear relaxation of
by column generation.
JjY
JjY
IinYa
YP
j
j
Jj
ijij
Jj
j






,integer
,0
,
min:
JjY
IinYa
YLP
j
Jj
ijij
Jj
j





,0
,
min:
J
,P
,LP
Minimize the number
of standard rolls used

5. COLUMN GENERATION 5
The Cutting Stock
Problem ...
Given a subset
and the dual multipliers
the reduced cost of
any new patterns
must satisfy:
otherwise, is optimal.
JjY
IinYa
YLP
j
Jj
ijij
Jj
j





,0
,
min:
JJ'
,),'( IiJ
ii

;01min
'\



Ii
iij
JJj
a
LP

6. COLUMN GENERATION 6
The Cutting Stock
Problem ...
Reduced costs for
are non negative, hence:
is a decision variable:
the number of times
item i is selected in a
new pattern.
The Column Generator
is a Knapsack Problem.
'Jj
Iia
Lal
a
a
a
i
Ii
ii
Ii
ii
Ii
iji
Jj
Ii
iji
JJj















integer, 0
1min
1min
1min
'\



ia
Iia
Lal
a
i
Ii
ii
Ii
ii







integer, 0
max

7. COLUMN GENERATION 7
Basic
Observations
Keep
the coupling constraints
at a superior level,
in a Master Problem;
this with the goal
of obtaining a
Column Generator which
is rather easy to solve.
At an inferior level,
solve the
Column Generator,
which is often separable
in several independent
sub-problems;
use a specialized
algorithm that exploits
its particular structure.

8. COLUMN GENERATION 8
LP
Column Generation
Optimality Conditions: primal feasibility
complementary slackness
dual feasibility
MASTER PROBLEM
Columns Dual Multipliers
COLUMN GENERATOR
(Sub-problems)

9. COLUMN GENERATION 9
Historical
Perspective
G.B. Dantzig &
P. Wolfe
Decomposition Principle
for Linear Programs.
Oper. Res. 8, 101-111.
(1960)
Authors give credit to:
L.R. Ford & D.R. Fulkerson
A Suggested Computation
for Multi-commodity flows.
Man. Sc. 5, 97-101.
(1958)

10. COLUMN GENERATION 10
Historical Perspective :
a Dual Approach
J.E. Kelly The Cutting Plane Method
for Solving Convex Programs.
SIAM 8, 703-712.
(1960)
DUAL MASTER PROBLEM
Rows Dual Multipliers
ROW GENERATOR
(Sub-problems)

11. COLUMN GENERATION 11
Dantzig-Wolfe Decomposition :
the Principle
)(,0
)(,0
1
:asrewritten )(
)(p
p
)()(









r
p
dxx
XConvx
r
p
r
rr
p
pp




rays extreme:)(
points extreme :)(
sets define ),(On


Xconv
Xx
bAx
cxP


min:

12. COLUMN GENERATION 12
Dantzig-Wolfe Decomposition :
Substitution
)(,0
)(,0
1
)(
)(min:
)(
)( )(
)( )(






 
 

 
 
r
p
bdxA
dxcP
r
p
p
p
p r
rrpp
p r
rrpp





Xx
bAx
cxP


min:

13. COLUMN GENERATION 13
)(,0
)(,0
1
)()(
)()(min:
)(
)( )(
)( )(






 
 

 
 
r
p
bAdAx
cdcxP
r
p
p
p
p r
rrpp
p r
rrpp





Dantzig-Wolfe Decomposition :
The Master Problem
)(,0
)(,0
1
)(
)(min:
)(
)( )(
)( )(






 
 

 
 
r
p
bdxA
dxcP
r
p
p
p
p r
rrpp
p r
rrpp





The Master Problem

14. COLUMN GENERATION 14
Dantzig-Wolfe Decomposition :
The Column Generator
Given the current
dual multipliers for a
subset of columns :
coupling constraints
convexity constraint
generate (if possible)
new columns with
negative reduced cost :
)(
)(min
0
Xconvx
Axcx

 
)(
,0)(
if points extreme
otherwise
)(
,0)(
if rays extreme
0




psomefor
Axcx
rsomefor
dAc
pp
r


)(
o

15. COLUMN GENERATION 15
)(
,)(
if points extreme
otherwise
)(
,0)(
if rays extreme
0




psomefor
bbAxcx
rsomefor
dAc
pp
r


Remark
)(
,0)(
if points extreme
otherwise
)(
,0)(
if rays extreme
0




psomefor
Axcx
rsomefor
dAc
pp
r



16. COLUMN GENERATION 16
Dantzig-Wolfe Decomposition :
Block Angular Structure
Exploits the structure of
many sub-problems.
Similar developments
& results.
KkXx
bxA
xcP
kk
Kk
kk
Kk
kk





,
min:

17. COLUMN GENERATION 17
Dantzig-Wolfe Decomposition :
Algorithm
Optimality Conditions: primal feasibility
complementary slackness
dual feasibility
MASTER PROBLEM
Columns Dual Multipliers
COLUMN GENERATOR
(Sub-problems)

18. COLUMN GENERATION 18
Given the current
dual multipliers
(coupling constraints)
(convexity constraint),
a lower bound can
be computed at
each iteration, as
follows:
Dantzig-Wolfe Decomposition :
a Lower Bound
Xx
bAxcx
Xx
Axcxb




)(min
)(min)(
00


)(
o
Current solution value
+ minimum
reduced cost column

19. COLUMN GENERATION 19
).(max using obtained is boundlower best The
.),()(
;)(,0)(
:on boundlower a provides
)(
)(min)(





L
otherwisepsomeforbAxcx
rsomefordAcif
P
Xconvx
bAxcxL
pp
r




Lagrangian Relaxation Computes
the Same Lower Bound
Xx
bAx
cxP


min:

20. COLUMN GENERATION 20
Dantzig-Wolfe vs Lagrangian
Decomposition Relaxation
Essentially utilized
for Linear Programs
Relatively difficult to
implement
Slow convergence
Rarely implemented
Essentially utilized
for Integer Programs
Easy to implement with
subgradient adjustment
for multipliers 
No stopping rule !
 6% of OR papers

21. COLUMN GENERATION 21
Equivalencies
Dantzig-Wolfe
Decomposition &
Lagrangian Relaxation
if both have the same
sub-problems
In both methods, coupling
or complicating constraints
go into a
DUAL MULTIPLIERS
ADJUSTMENT PROBLEM :
in DW : a
LP Master Problem
in Lagrangian Relaxation :
)(max 

L

22. COLUMN GENERATION 22
Equivalencies ...
Column Generation corresponds to the solution
process used in Dantzig-Wolfe decomposition.
This approach can also be used directly by
formulating a Master Problem and sub-problems
rather than obtaining them by decomposing a
Global formulation of the problem. However ...

23. COLUMN GENERATION 23
Equivalencies ...
… for any Column
Generation scheme,
there exits
a Global Formulation
that can be decomposed
by using a
generalized Dantzig-
Wolfe decomposition
which results in the
same Master and sub-
problems.
The definition of the
Global Formulation
is not unique.
A nice example:
The Cutting Stock
Problem

24. COLUMN GENERATION 24
. ,integer,0
,10
,
,
min
KkIiX
KkorY
KkYLXl
IinX
Y
k
i
k
k
Ii
k
ii
i
Kk
k
i
Kk
k










The Cutting Stock Problem :
Kantorovich (1960/1939)
: set of
available rolls
: binary variable,
1 if roll k is cut,
0 otherwise
: number of times
item i is cut
on roll k
K
k
Y
k
i
X

25. COLUMN GENERATION 25
The Cutting Stock Problem :
Kantorovich ...
Kantorovich’s LP
lower bound is weak:
However, Dantzig-Wolfe
decomposition provides
the same bound as the
Gilmore-Gomory LP
bound if sub-problems
are solved as ...
integer Knapsack
Problems, (which
provide extreme point
columns).
Aggregation of
identical columns
in the Master Problem.
Branch & Bound
performed on
||K
.
k
iX
./Lnl
Ii
ii


26. COLUMN GENERATION 26
The Cutting Stock Problem :
Valerio de Carvalhó (1996)
Network type formulation on graph ),(AN
}1,...,1,0),1,{(},0:),{(
},1,...,2,1,0{


LuuuIiluvandLvuvuA
LLN
i 
Example with , and 3,2
21
ll5L

27. COLUMN GENERATION 27
AvuX
zX
LvXX
zX
IinX
Z
uv
Lu
uL
vu uv
vuuv
v
v
i
Aluu
luu
i
i











),( integer, 0
,
}1,,2,1{,0
,
,
min
),(
),( ),(
),0(
0
),(
,

The Cutting Stock Problem :
Valerio de Carvalhó ...

28. COLUMN GENERATION 28
The Cutting Stock Problem :
Valerio de Carvalhó ...
The sub-problem is a
shortest path problem
on a acyclic network.
This Column Generator
only brings back
extreme ray columns,
the single extreme point
being the null vector.
The Master Problem
appears without the
convexity constraint.
The correspondence
with Gilmore-Gomory
formulation is obvious.
Branch & Bound
performed on .
uv
X

29. COLUMN GENERATION 29
The Cutting Stock Problem :
Desaulniers et al. (1998)
It can also be viewed as a
Vehicle Routing Problem
on a acyclic network
(multi-commodity flows):
Vehicles Rolls
Customers Items
Demands
Capacity
Column Generation tools
developed for Routing
Problems can be used.
Columns correspond to
paths visiting items the
requested number of
times.
Branch & Bound
performed on
iinl
L
.
k
ij
X

30. COLUMN GENERATION 30
integer
min:
x
Xx
bAx
cxIP


IP
Column Generation
integer
)(,0
)(,0
1
)()(
)()(min:
)()(
)(
)( )(
)( )(
x
dxx
r
p
bAdAx
cdcxIP
r
rr
p
pp
r
p
p
p
p r
rrpp
p r
rrpp


 
 


 
 













31. COLUMN GENERATION 31
Integrality
Property
The sub-problem
satisfies the
Integrality Property
if it has an integer
optimal solution for any
choice of linear
objective function,
even if the integrality
restrictions on the
variables are relaxed.
In this case,
otherwise
i.e., the solution process
partially explores the
integrality gap.
)()(max LPvL
)()(max)( IPvLLPv  

32. COLUMN GENERATION 32
Integrality
Property ...
In most cases, the
Integrality Property is a
undesirable property!
Exploiting the non trivial
integer structure reveals
that ...
… some overlooked
formulations become
very good when a
Dantzig-Wolfe
decomposition process is
applied to them.
The Cutting Stock Problem
Localization Problems
Vehicle Routing Problems
...

33. COLUMN GENERATION 33
IP Column Generation :
Branch-and-...
Branch-and-Bound :
branching decisions
on a combination of the
original (fractional) variables
of a Global Formulation on
which Dantzig-Wolfe
Decomposition is applied.
Branch-and-Cut :
cutting planes defined
on a combination of the
original variables;
 at the Master level, as
coupling constraints;
 in the sub-problem, as
local constraints.

34. COLUMN GENERATION 34
IP Column Generation :
Branch-and-...
Branching &
Cutting decisions
integer
min:
x
Xx
bAx
xcIP


Dantzig-Wolfe decomposition
applied at all decision nodes
{ }

35. COLUMN GENERATION 35
IP Column Generation:
Branch-and-...
Branch-and-Price :
a nice name
which hides
a well known
solution process
relatively easy to apply.
For alternative methods,
see the work of
S. Holm & J. Tind
C. Barnhart, E. Johnson,
G. Nemhauser, P. Vance,
M. Savelsbergh, ...
F. Vanderbeck & L. Wolsey

36. COLUMN GENERATION 36
Application to Vehicle Routing and
Crew Scheduling Problems (1981 - …)
Global Formulation :
Non-Linear Integer
Multi-Commodity Flows
Master Problem :
Covering & Other
Linking Constraints
Column Generator :
Resource Constrained
Shortest Paths
 J. Desrosiers, Y. Dumas, F.
Soumis & M. Solomon
Time Constrained Routing and
Scheduling Handbooks
in OR & MS, 8 (1995)
 G. Desaulniers et al. A
Unified Framework for
Deterministic Vehicle Routing
and Crew Scheduling Problems
T. Crainic & G. Laporte (eds) Fleet
Management & Logistics (1998)

37. COLUMN GENERATION 37
Resource Constrained
Shortest Path Problem on G=(N,A)



Ni Rr
r
ii
Aji
ijij TxcMin 
),(
doidioixx
Aijj
ij
Ajij
ij ,,0;,1;,1
),(:),(:


RrAjiTTfx
r
jiijij
 ,),(,0))((
Ajix
RrNibxTax
ij
r
i
Ajij
ij
r
i
r
i
Ajij
ij

 

),(,binary
,,)()(
),(:),(:
P(N, A) :

38. COLUMN GENERATION 38
Integer Multi-Commodity
Network Flow Structure
 
 

Kk Ni Rr
kr
i
k
i
Aji
k
ij
k
ij
kk
TxcMin )(
),(

MmbTaxa
Nibx
m
Kk
kr
i
Ni
kr
im
Aji
k
ij
k
ijm
Kk
k
i
Kk Ajij
k
ij
kk
k


 

 
 
,)(
,)(
,
),(
,
),(:

KkANPTx
kkkk
 ),,(),(

39. COLUMN GENERATION 39
Vehicle Routing and Crew
Scheduling Problems ...
Sub-Problem
is strongly NP-hard
It does not posses the
Integrality Property
Paths  Extreme points
Master Problem results in
Set Partitioning/Covering
type Problems
Branching and Cutting decisions are
taken on the original network flow,
resource and supplementary variables

40. COLUMN GENERATION 40
IP Column Generation :
Acceleration Techniques
on the Column Generator
Master Problem
Global Formulation
With Fast Heuristics
Re-Optimizers
Pre-Processors
To get Primal
& Dual Solutions
Exploit all the Structures

41. COLUMN GENERATION 41
IP Column Generation :
Acceleration Techniques ...
Multiple Columns :
selected subset close to
expected optimal solution
Partial Pricing in case of
many Sub-Problems :
as in the Simplex Method
Early & Multiple Branching
& Cutting : quickly gets
local optima
Primal Perturbation &
Dual Restriction : to
avoid degeneracy and
convergence difficulties
Branching & Cutting :
on integer variables !
Branch-first, Cut-second
Approach :
exploit solution structures
Link all the Structures Be Innovative !

42. COLUMN GENERATION 42
Stabilized Column Generation
0
min


x
bAx
cx
cA
b

max
21
max
dd
cA
b





Restricted Dual
2211
21
0,0
0
min
 


yy
x
byyAx
cx
Perturbed Primal

2211
21
2211
0,0
0
min
 



yy
x
byyAx
ydydcx
Stabilized Problem

43. COLUMN GENERATION 43
Concluding Remarks
 DW Decomposition is
an intuitive framework
that requires all tools
discussed to become
applicable
 “easier” for IP
 very effective in
several applications
Imagine what could be
done with theoretically
better methods such as
… the Analytic Center
Cutting Plane Method
(Vial, Goffin, du Merle,
Gondzio, Haurie, et al.)
which exploits recent
developments in interior
point methods,
and is also compatible with
Column Generation.

44. COLUMN GENERATION 44
“Bridging Continents and Cultures”
F. Soumis
M. Solomon
G. Desaulniers
P. Hansen
J.-L. Goffin
O. Marcotte
G. Savard
O. du Merle
O. Madsen
P.O. Lindberg
B. Jaumard
M. Desrochers
Y. Dumas
M. Gamache
D. Villeneuve
K. Ziarati
I. Ioachim
M. Stojkovic
G. Stojkovic
N. Kohl
A. Nöu
… et al.
Canada, USA, Italy,
Denmark, Sweden,
Norway, Ile Maurice,
France, Iran, Congo,
New Zealand, Brazil,
Australia, Germany,
Romania, Switzerland,
Belgium, Tunisia,
Mauritania, Portugal,
China, The Netherlands,
...