Column Generation

(1)

Column Generation

By

Soumitra Pal

Under the guidance of Prof. A. G. Ranade

(2)

Agenda

• Introduction

• Basics of Simplex algorithm

• Formulations for the CSP

• (Delayed) Column Generation

• Branch-and-price

• Flow formulation of CSP & solution

• Conclusions

(3)

Cutting Stock Problem

• Given larger

raw paper rolls

• Get final rolls of smaller widths

10

5 3

(4)

Cutting Stock Problem (2)

• Raw width (W) = 10

• No of finals given below

i Width (w_i) Quantity (b_i)

1 3 9

2 5 79

3 6 90

4 9 27

• Minimize total no of raws reqd. to be cut

(5)

Agenda

• Introduction

• Basics of Simplex algorithm

• Conclusions

(6)

5x1 - 8x2 ≥ -80 -5x1 - 4x2 ≥ -100 -5x1 - 2x2 ≥ -80 -5x1 + 2x2 ≥ -50

Min -x1 -x2

Objective/

Cost fn

Constraints

(7)

(10,0)

(13,5) (12,10)

(8,15)

(0,10)

5x1 - 8x2 ≥ -80 -5x1 - 4x2 ≥ -100 -5x1 - 2x2 ≥ -80 -5x1 + 2x2 ≥ -50

(8)

-x1-x2 = -10 -x1-x2 = -20 -x1-x2 = -30 Cost decreases

in this direction

(9)

(10,0)

(13,5) (12,10)

(8,15)

(0,10)

Simplex method

(10)

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

b x

a x

a

b x

a x

a

x c x

c x

c

i

m l

ml m

m

l n

l n l n

≥

≥ +

+ +

≥ +

+ +

≥ +

+ +

+

L M

L

(11)

0 :

s.t.

0 0

0 Min

1 2 1

1

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

c x

c

L

L M

L L

L

(12)

0 :

s.t.

Min

≥

= x

b Ax

cx

(13)

(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 - 2x2 ≥ -80 -5x1 + 2x2 ≥ -50

5x1 - 8x2 ≥ -80 -5x1 - 4x2 ≥ -100

(14)

[ ]

' 1

'

' 1

1 '

' ' '

1 1

equation, previous

in it Putting

variable basic

- non one

increase corner,

next out

find To

0

0 , min 0

N B

B

N B

B

B B

B

B B

B N

B

Nx B

x x

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

−

=

=> = −

=> + =

⎥⎦

⎢ ⎤

⎣

= ⎡

⎥ =

⎦

⎢ ⎤

⎣

⎡

=

=> =

=>

≥

⎥ =

⎦

⎢ ⎤

⎣

= ⎡

⎥⎦

⎢ ⎤

⎣

= ⎡

(15)

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

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

(16)

• 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

.

variable basic

new with

mutilpies

that of

column the

be 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

=

= +

−

(17)

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

_N

−

_B ⁻¹

' 1

'

N B

B

x B Nx

x = −

⁻

(18)

Smart way of doing

variable leaving

about info

gives

gives ,

of column the

is where

cost reduced

and gives

gives

d x

d N

a a

Bd

yN c

y c

yB

x b

Bx

B

N B

B B

= −

= =

(19)

y d

Start

(20)

y d

Reduced cost vector

(21)

y d

Selection of non-basic variable

(22)

y d

y vector

(23)

y d

Selection of leaving basic variable

(24)

Preparation for next step

y d

(25)

y d

Entering variable in 2

^nd

iteration

(26)

y d

Leaving variable in 2

^nd

iteration

(27)

y d

Preparation for 3

^rd

iteration

(28)

y d

Final iteration

(29)

Done so far

• Basics of (revised) Simplex algorithm

– Formulation

– Corners, basic variables, non-basic variables – How to move from corner to corners

– Optimal value

(30)

Agenda

• Introduction

• Formulations for the CSP

• Conclusions

(31)

raw k

from cut

width i

of finals of

no.

otherwise 0

used, is

raw k

if 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

: s.t.

Min

th

th th

1 1 1

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

K K

K K K

=

≥ ==

=

≤

=

≥

∑

=

Kantorovich formulation

First step to solution - Formulation

(32)

Kantorovich formulation example

1 2 3 4

1

, 4

3

, 1

0

, 1

, 4

2 1

13 21

11

4 2

3 1

=

= = = = =

=

∑

k

k k

k x

x

x x

x

y y

K

(33)

LP relaxation

• Integer programming is hard

• Convert it to a linear program

raw k

from cut

width i

of finals of

no.

otherwise 0

used, is

raw k

if 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

: s.t.

Min

th

th th

1 1 1

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

K K

K K K

=

≥ ==

=

≤

=

≥

∑

=

0 ≤ y_k ≤ 1

(34)

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?

(35)

j pattern from

cut

width i

of finals of

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

i J

j

j ij J j

j

a x

J j

x

m i

b x

a x

∈

∀

≥

=

∑

≥

∑

∈

K

Another Formulation

Gilmore-Gomory Formulation

(36)

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

≥

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

27 90 79 9

0 0

1

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

9 8 7 6 5 4 3 2 1

4 3 2 1

x x x x x x x x x

w w w w

3*1 + 5*0 + 6*1 + 9*0 = 9 ≤ 10

Example formulation

(37)

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

(38)

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

(39)

Done so far

– Formulation

– Optimal value

• Formulation of the CSP

– LP relaxation – Bounds

(40)

Agenda

• Introduction

• (Delayed) Column Generation

• Conclusions

(41)

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

_N

−

_B ⁻¹

or

_N

−

(42)

Column Generation (2)

• In terms of columns, we need to find

• That is equivalent to finding a such that

• For cutting stock problem, c_j=1, hence it is equivalent to

• With implicit constraint

• Pricing sub-problem

} of

column a

is

| {

min

arg

j

c

_j

− ya

_j

a

_j

N

} of

column a

is

| )

(

min{ c a − ya a A

} 1

|

max{ ya ya >

W

wa ≤

(43)

Column Generation (3)

Any New Columns?

STOP (LP Optimal)

Solve

Restricted Master Problem (RMP)

Solve Pricing Problem Update RMP with

New Columns

No Yes

(44)

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

≥

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

27 90 79 9

0 0

1

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

9 8 7 6 5 4 3 2 1

4 3 2 1

x x x x x x x x x

w w w w

Example formulation

(45)

[ ] [ ]

[ ]

^T

B B

a

a a

y yB

x B

C

0 1

find can

we g,

programmin dynamic

or n enumeratio Using

10 9

6 5

3

constraint knapsack

Given

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

2 0

0 0

0 3

,

27 90 79 9

4 3

2 1

4 3

2 1

=

≤ +

+ +

≥ +

+ +

=

=>

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

(46)

[ ]

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

= −

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

= −

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎦ =

⎢⎣ ⎤

= ⎡

⎥⎦⎤

⎢⎣⎡

=

=>

=

27 81

5 . 39

9

27 1 . 9 90

5 . 39

9

27 . 90

5 . , 39

1 0

0 0

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

(47)

[ ] [ ]

5 . 156 27

81 5

. 39 9

Solution

optimal already

is Hence

1 subproblem

of solution get

not can

We

10 9

6 5

3

costraint knapsack

Given

1 .

2 1 . 1

0 maximize to

need we

1 1

2 / 1 0

1 1

27 81

5 . 39

9 ,

1 0

0 0

0 1

0 0

2 0

0 0

0 1

4 3

2 1

4 3

2 1

= +

+ +

=

>

≤ +

+ +

≥ +

+ +

=

=>

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

⎥⎥

⎦

⎤

⎢⎢

⎣

⎡

=

B

x

a a

y yB

x B

(48)

Done so far

– Formulation

– Optimal value

• Formulation of the CSP

– LP relaxation – Bounds

• Delayed column generation

– Restricted master problem

– Sub-problem to generate column – Repeated till optimal

(49)

Agenda

• Introduction

• Branch-and-price

• Conclusions

(50)

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 x₂ is 39.5

• One way is to rounding

(51)

• 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

(52)

• 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

(53)

Done so far

• Basics of (revised) Simplex algorithm – Formulation

– 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

(54)

Agenda

• Introduction

• Flow formulation of CSP & solution

• Conclusions

(55)

Flow formulation

• Bin packing problem

• Similar to the cutting stock problem

bin items

(56)

w₂ w₂ w₂ w₂

w₁ w₁ w₁

loss loss loss loss loss

0 1 2 3 4 5

w₂ w₂

0 1 2 3 4 5

loss

Example

• Bin capacity W = 5

• Item sizes – w₁=3 and w₂=2

(57)

Formulation equations

• Problem is equivalent to finding minimum flow between nodes 0 & W

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

d

d L

K

(58)

• 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

(59)

w₂ w₂ w₂ w₂

w₁ w₁ w₁

loss loss loss loss loss

1 2 3 4

0

5

Invalid as per rule 2 Invalid as per rule 1

w₂ w₂ w₂

w₁

loss loss loss

0 1 2 3 4 5

(60)

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)

(61)

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

(62)

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

(63)

Acknowledgements

• Valerio de Carvalho for borrowing some of his explanations exactly

• http://www-

fp.mcs.anl.gov/otc/Guide/CaseStudies/s implex/applet/SimplexTool.html for the java applet

• AMPL & CPLEX tools

• My guide

(64)

(65)

Thank you!

(66)