Column Generation
By
Soumitra Pal
Under the guidance of Prof. A. G. Ranade
Agenda
• Introduction
• Basics of Simplex algorithm
• Formulations for the CSP
• (Delayed) Column Generation
• Branch-and-price
• Flow formulation of CSP & solution
• Conclusions
Cutting Stock Problem
• Given larger
raw paper rolls
• Get final rolls of smaller widths
10
5 3
Cutting Stock Problem (2)
• Raw width (W) = 10
• No of finals given below
i Width (wi) Quantity (bi)
1 3 9
2 5 79
3 6 90
4 9 27
Agenda
• Introduction
• Basics of Simplex algorithm
• Formulations for the CSP
• (Delayed) Column Generation
• Branch-and-price
• Flow formulation of CSP & solution
• Conclusions
5x1 - 8x2 ≥ -80 -5x1 - 4x2 ≥ -100 -5x1 - 2x2 ≥ -80 -5x1 + 2x2 ≥ -50
Min -x1 -x2 Objective/
Cost fn
Constraints
(10,0)
(13,5) (12,10)
(8,15)
(0,10)
5x1 - 8x2 ≥ -80 -5x1 - 4x2 ≥ -100 -5x1 - 2x2 ≥ -80 -5x1 + 2x2 ≥ -50
Cost decreases in this
direction
(10,0)
(13,5) (12,10)
(8,15)
(0,10)
Simplex method
contraints of
no.
variables of
no.
0 :
s.t.
Min
1 2 1
1
2 2
2 22 1
21
1 1
2 12 1
11
2 2 1
1
m l
x
b x
a x
a x
a
b x
a x
a x
a
b x
a x
a x
a
x c x
c x
c
i
m l
ml m
m
l n
l n l n
0 :
s.t.
0 0
0 Min
1 2 1
1
2 2
2 2
22 1
21
1 1
1 2
12 1
11
2 1
2 2 1
1
i
m n
l ml m
m
l l
n
l l
n
n l
l l
n
x
b x
x a x
a x
a
b x
x a x
a x
a
b x
x a x
a x
a
x x
x x
c x
c x
c
0 :
s.t.
Min
x
b Ax
cx
(10,0,130,50,30,0)
(13,5,110,10,0,0) (12,10,60,0,0,10)
(8,15,0,0,10,40)
(0,10,0, 60,60,70)
(0,0,80, 100,80,50)
Basic & non-basic 5x1 - 8x2 ≥ -80 -5x1 - 4x2 ≥ -100 -5x1 - 2x2 ≥ -80 -5x1 + 2x2 ≥ -50
' 1
1 '
1 '
1 '
' ' '
1 1
1 1
equation, previous
in it Putting
variable basic
- non one
increase corner,
next out
find
To 0
0
0 , min 0
N B
N B
B
B B
B B
B
B B
B N
B
Nx B
b B x
b B Nx
B x
x x x
b x B
N B
I
b B c x
c cx
b B x
b Bx
x x b
N B
Ax
c x c
cx
N B
c c
c
x N B
c c
cx cx
x N B
c c
x c x
c x
c cx
x c
Nx B
x c
x c x
c cx
B N
N B
N
N B
N B
B N
N B
B
N N N
B B
N N
B B
1
' 1
'
' 1
' '
'
' '
1 '
' '
cost reduced
called is
bracket in
term The
) (
cost in
Change ( )
) (
cost New
• If all elements of it are non-negative, it is already optimal
• Otherwise choose the non-basic variable corresponding to most negative value to enter the basic
• How to find out outgoing basic variable?
of component kth
) (
of component kth
of Min value
0.
becomes of
component )
k (say
one until
increased be
can It
. with new basic variable mutilpiesbe the column of that Let
1
' th
1 1
' 1
'
d
x b
B
x x
N B
d
b B
Nx B
x
B B
i
N B
Few steps of simplex algorithm
• Compute reduced cost
• If all >= 0, optimal stop.
• Otherwise choose the most negative component
• Corresponding variable enters basis
• Compute the ratios for finding out leaving basis
• Update basic variables and B for next step
N B
c
c
N
B 1' 1
'
N B
B
x B Nx
x
Smart way of doing
variable leaving
about info
gives
gives ,
of column the
is
wheregivesgives and reduced cost d
x a a N d
BdyB cb xy c yN
Bx
B
N B
B B
y d
Start
y d
Reduced cost vector
y d
Selection of non-basic variable
y d
y vector
y d
Selection of leaving basic variable
Preparation for next step
y d
y d
Entering variable in 2
nditeration
y d
Leaving variable in 2
nditeration
y d
Preparation for 3
rditeration
y d
Final iteration
Done so far
• Basics of (revised) Simplex algorithm
– Formulation
– Corners, basic variables, non-basic variables – How to move from corner to corners
– Optimal value
Agenda
• Introduction
• Basics of Simplex algorithm
• Formulations for the CSP
• (Delayed) Column Generation
• Branch-and-price
• Flow formulation of CSP & solution
• Conclusions
raw k
from cut
width i
of finals of
no.
otherwise
0if k raw is used, 1
width a
for index i
raw a
for index k
widths different
of no.
m raws
available of
no.
K
, , 1 ,
, integer 1
and 0
, , 1 1
or 0
, , 1
, , 1
: s.t.
Min
th
th th
1 1 1
ik k
ik k
k m
i
ik i
i K
k
ik K k
k
x y
m i
K x k
K k
y
K k
Wy x
w
m i
b x
y
First step to solution - Formulation
Kantorovich formulation
Kantorovich formulation example
1 2 3 4
1
, 4
3
, 1
,
1, 1, 0
4
13 21
11
4 2
3 1
x xx x
x y y y y
K
LP relaxation
• Integer programming is hard
• Convert it to a linear program
raw k
from
cut of finalsof i width no.
otherwise
0if k rawisused, 1
width a
for index i
raw a for index k
widths different
of no.
m raws
available of
no.
K
, , 1 ,
, integer 1
and 0
, , 1 1
or 0
, , 1
, , 1
: s.t.
Min
th
th th
1 1 1
ik k
ik k
k m
i
ik i
i K
k ik K k
k
x y
m i
K x k
K k
y
K k
Wy x
w
m i
b x
y
0 ≤ yk ≤ 1
LP relaxation (2)
• LP relaxation is poor
• For our example, optimal LP objective is 120.5
• The optimal integer objective solution value is 157
• Gap is 36.5
• It can be as bad as ½ of the integer solution
• Can we get a better LP relaxation?
j pattern from
cut of finals of i width no.
j pattern in
cut raws
of no.
patterns possible
all of set J
pattern cutting
a j
widths different
of no.
m
width a
for index
i
integer
and 0
, ,
1
: s.t.
Min
th ij
j
j
i J
j
j ij J j
j
a x
J j
x
m i
b x
a x
Another Formulation
Gilmore-Gomory Formulation
27 90 79 9
0 0
0 0
0 0
0 0
1
0 0
0 0
0 0
1 1
0
0 0
0 1
2 1
0 0
0
3 2
1 1
0 0
1 0
0 : 9
: 6
: 5
: 3
8 7 6 5 4 3 2 1
4 3 2 1
x x x x x x x x
w w w w
Example formulation
3*1 + 5*0 + 6*1 + 9*0 = 9 ≤ 10
LP relaxation of Gilmore-Gomory
• LP relaxation is better
• For our example, 156.7
• Integer objective solution, 157
• Gap is 0.3
• Conjecture: Gap is less than 2 for practical cutting stock problems
Issues
• The number of columns are exponential
• Optimal value is still not integer
• Gilmore-Gomory proposed an ingenuous way of working with less columns
• Branch-and-price to solve the other problem
Done so far
• Basics of (revised) Simplex algorithm
– Formulation
– Corners, basic variables, non-basic variables – How to move from corner to corners
– Optimal value
• Formulation of the CSP
– LP relaxation – Bounds
Agenda
• Introduction
• Basics of Simplex algorithm
• Formulations for the CSP
• (Delayed) Column Generation
• Branch-and-price
• Flow formulation of CSP & solution
• Conclusions
Column Generation
• In pricing step of simplex algorithm one basic variable leaves and one non-basic variable enters the basis
• This decision is made from the reduced cost vector
• The component with most negative value determines the entering variable
yN c
N B
c
c
N
B 1or
N
Column Generation (2)
• In terms of columns, we need to find
• That is equivalent to finding a such that
• For cutting stock problem, cj=1, hence it is equivalent to
• With implicit constraint
} of
column a
is
| {
min
arg
jc
j ya
ja
jN
} of
column a
is
| )
(
min{ c a ya a A
} 1
|
max{ ya ya
W
wa
Column Generation (3)
Any New Columns?
STOP (LP Optimal)
Solve
Restricted Master Problem (RMP)
Solve Pricing Problem Update RMP with
New Columns
No Yes
27 90 79 9
0 0
0 0
0 0
0 0
1
0 0
0 0
0 0
1 1
0
0 0
0 1
2 1
0 0
0
3 2
1 1
0 0
1 0
0 : 9
: 6
: 5
: 3
8 7 6 5 4 3 2 1
4 3 2 1
x x x x x x x x
w w w w
Example formulation
TB B
a
a a
a a
a a
a a
y yB
x B
C
0 1
0 1
find can
we g,
programmin dynamic
or n enumeratio Using
10 9
6 5
3Given knapsack constraint
1 .
1 .
2 1 1 3
1 maximize to
need we
1 1
2 / 1 3
/ 1 1
1 1
1
27 90
5 . 39
3
1 / 27
1 / 90
2 / 79
3 / 9 ,
1 0
0 0
0 1
0 0
0 0
2 0
0 0
0 3
,
27 90 79 9
4 3
2 1
4 3
2 1
27 81
5 . 39
9
27 1 . 9 90
5 . 39
9
27 . 90
5 . , 39
1 0
0 0
0 1
0 1
0 0
2 0
0 0
0 1
replaced is
B in column first
, 9
* 90
* 9
* 1
/ 90 3 *
/ 1 3 /
0 1
3 0 1
d3
t t x
B t
d x
d a
Bd
B
T T
B
T
5 . 156 27
81 5
. 39 9
Solution
optimal already
is
HenceWe can not get solution of subproblem 1 10
9 6
5
3Given knapsack costraint
1 .
1 .
2 1 . 1
0 maximize to
need we
1 1
2 / 1 0
1 1
1 1
27 81
5 . 39
9 ,
1 0
0 0
0 1
0 1
0 0
2 0
0 0
0 1
4 3
2 1
4 3
2 1
B
B
x
a a
a a
a a
a a
y yB
x B
Done so far
• Basics of (revised) Simplex algorithm
– Formulation
– Corners, basic variables, non-basic variables – How to move from corner to corners
– Optimal value
• Formulation of the CSP
– LP relaxation – Bounds
• Delayed column generation
– Restricted master problem
– Sub-problem to generate column – Repeated till optimal
Agenda
• Introduction
• Basics of Simplex algorithm
• Formulations for the CSP
• (Delayed) Column Generation
• Branch-and-price
• Flow formulation of CSP & solution
• Conclusions
Integer solution
• A formulation of the problem which gives
‘good’ LP relaxation
• Solved the LP relaxation using column generation
• But, the LP relaxation is not the ultimate goal, we need integer solution
• In the example x2 is 39.5
• One way is to rounding
• What to do if there are multiple fractional variables?
• The method commonly followed is branch - and-bound technique of solving integer
programs
• Basic fundae
– create multiple sub-problems with extra constraints
– solve the sub-problems using column generation – take the best of solutions to the sub problems
• Key is the rules of dividing into sub
problems (this is called branching strategy)
• Things to look into
– Branching rule does not destroy column generation sub problem property
– Efficiency of the process
• Ingenuity of the formulation and branching strategy
• Use of running bounds to prune (fathomed)
• This technique is called branch-and-price
• We see another formulation next
Done so far
• Basics of (revised) Simplex algorithm
– Formulation
– Corners, basic variables, non-basic variables – How to move from corner to corners
– Optimal value
• Formulation of the CSP
– LP relaxation – Bounds
• Delayed column generation
– Restricted master problem
– Sub-problem to generate column – Repeated till optimal
• Branch-and-price
– Basic fundae
Agenda
• Introduction
• Basics of Simplex algorithm
• Formulations for the CSP
• (Delayed) Column Generation
• Branch-and-price
• Flow formulation of CSP & solution
• Conclusions
Flow formulation
• Bin packing problem
• Similar to the cutting stock problem
bin items
w2 w2 w2 w2
w1 w1 w1
loss loss loss loss loss
0 1 2 3 4 5
w2 w2
loss
Example
• Bin capacity W = 5
• Item sizes – w1=3 and w2=2
Formulation equations
• Problem is equivalent to finding minimum flow between nodes 0 & W
0 integer
0 integer
, ,
2 , 1
,
1 ,
, 2 , 1 ,
0
0 ,
: s.t.
Min
) (
) (
z x
m d
b x
W j
z
W i
j z
x x
z
ij
A w
k k
d w
k k
A jk
jk A
ij
ij
d
d
• Issue of symmetry in the graph
• 3 rules to reduce symmetry
1. Arcs are specified according to decreasing width
2. A bin can never start with a loss
3. Number of consecutive arcs corresponding to a single item size must not exceed
number of orders
w2 w2 w2 w2
w1 w1 w1
loss loss loss loss loss
0 1 2 3 4
5
Invalid as per rule 2 Invalid as per rule 1
w2 w2 w2
w1
loss loss loss
0 1 2 3 4 5
Branch-and-price
• The sub-problem finds an longest unit flow path where cost of each arc is given by y vector
• Branching heuristics
– Xij >= ceil(xij) – Xij <= floor(xij)
Few other points
• Loss constraints from the LP relaxation value is equated with the sum of loss variables
• With the above constraint it can be shown that the solution will be always integral
• The algorithm uses this fact by incrementally adding the lower bound
• This is done finite no. of times
• No of new constraints are added is finite
• Algorithm runs in pseudo-polynomial time
Conclusions & Future work
• Column generation is a success story in large scale integer programming
• The flexibility to work with a few columns make real life problems tractable
• Ingenuous formulations and branching heuristics are used to improve efficiency
• Need to explore more applications with different heuristics
Acknowledgements
• Valerio de Carvalho for borrowing some of his explanations exactly
• http://www-fp.mcs.anl.gov/otc/Guide/Ca seStudies/simplex/applet/SimplexTool.h tml
for the java applet
• AMPL & CPLEX tools
• My guide