107
Approche décomposition de Dantzig-Wolfe en programmation entière: apport de l’ optimisation convexe Universit ´ e Bordeaux 1 INRIA - Rhones-Aples Universit ´ e de Gen ` eve Olivier Briant Claude Lemar ´ echal Claude Tadonki Philippe Meurdesoif Jean-Philippe Vial Krystel Monneris Cesar Beltran Sophie Michel Nancy Perrot Franc ¸ois Vanderbeck Funded by Inria New Investigation Grant “Convex Optimization and Dantzig-Wolfe Decomposition” http://www.math.u-bordeaux.fr/MAB/ODW/ 12 ` emes journ ´ ees du groupe MODE, Le Havre, 2004. – p.1/47

Approche décomposition de Dantzig-Wolfe en …fvanderb/papers/presMode2004.pdf · Approche décomposition de Dantzig-Wolfe en programmation entière: ... our projet of building a

  • Upload
    vunhi

  • View
    215

  • Download
    0

Embed Size (px)

Citation preview

Approche décomposition de Dantzig-Wolfe enprogrammation entière:

apport de l’ optimisation convexe

Universite Bordeaux 1 INRIA - Rhones-Aples Universite de GeneveOlivier Briant Claude Lemarechal Claude Tadonki

Philippe Meurdesoif Jean-Philippe VialKrystel Monneris Cesar BeltranSophie MichelNancy Perrot

Francois Vanderbeck

Funded by Inria New Investigation Grant

“Convex Optimization and Dantzig-Wolfe Decomposition”

http://www.math.u-bordeaux.fr/MAB/ODW/

12emes journees du groupe MODE, Le Havre, 2004. – p.1/47

PART 1: Background

Dantzig-Wolfe Decomposition

BaPCod: our projet of building a genericcode

12emes journees du groupe MODE, Le Havre, 2004. – p.2/47

Decomposition: Why

Divide and Conquer

complexity

size

+ + ...

12emes journees du groupe MODE, Le Havre, 2004. – p.3/47

Decomposition: Why

Divide and Conquer

+ + ...

complexity

size

Exploit the structure

12emes journees du groupe MODE, Le Havre, 2004. – p.4/47

Decomposition: When

� ��� ����� �

� � �

Difficult Constraints

12emes journees du groupe MODE, Le Havre, 2004. – p.5/47

Decomposition: When

� ��� ����� �

� � � Difficult Constraints

12emes journees du groupe MODE, Le Havre, 2004. – p.5/47

Decomposition: When

� ��� ����� �

� � � Difficult Constraints Ex: The Travelling Salesman Prob.

�������������������������������������

�����������������������������������

� � �� � � � � ��

12emes journees du groupe MODE, Le Havre, 2004. – p.6/47

Decomposition: When

� ��� ����� �

� � � Difficult Constraints

Linking Constraints

�����������

��� � � � � �

���

� � �

� � �

.... . .

...

� � �

�����������

12emes journees du groupe MODE, Le Havre, 2004. – p.7/47

Decomposition: When

� ���

�� �

� �� �

� � �

� �

� �Difficult Constraints

Linking Constraints

Multiple Sub-Systems ( variable splitting)

12emes journees du groupe MODE, Le Havre, 2004. – p.8/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Lagrangian:

Dual function:

Dual problem:

12emes journees du groupe MODE, Le Havre, 2004. – p.9/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Lagrangian:

� �� � � � � � �� � � � � ��� �

Dual function:

� � � � � � � ����� � � �� � � �

Dual problem:

� � � � � � � � � � �

12emes journees du groupe MODE, Le Havre, 2004. – p.9/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Reformulation (Variable Redefinition)

� � � �� � � �

LP�� �� � � �

LP

PSfrag replacements

LP

LP � �� � � �

LP

12emes journees du groupe MODE, Le Havre, 2004. – p.10/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Reformulation (Variable Redefinition)

Dynamic Cut Generation (Separation Sub-Problem)

�� �

LP

� � � �� �

LP� � � � � �

PSfrag replacements

LP

LP

12emes journees du groupe MODE, Le Havre, 2004. – p.11/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Reformulation (Variable Redefinition)

Dynamic Cut Generation (Separation Sub-Problem)

�� �

LP

� � � �� �

LP� � � � � �

PSfrag replacements

LP

LP

12emes journees du groupe MODE, Le Havre, 2004. – p.11/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Reformulation (Variable Redefinition)

Dynamic Cut Generation (Separation Sub-Problem)

�� �

LP

� � � �� �

LP� � � � � �

PSfrag replacements

LP

LP

12emes journees du groupe MODE, Le Havre, 2004. – p.11/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Reformulation (Variable Redefinition)

Dynamic Cut Generation (Separation Sub-Problem)

Dynamic Column Generation (Optimization Sub-Problem)

� � � �� � � � � � � � �� ��

� � �� ��

�� � � ��� ��

�� � �

Xlp

12emes journees du groupe MODE, Le Havre, 2004. – p.12/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Reformulation (Variable Redefinition)

Dynamic Cut Generation (Separation Sub-Problem)

Dynamic Column Generation (Optimization Sub-Problem)

� � � �� � � � � � � � �� ��

� � �� ��

�� � � ��� ��

�� � �

Xlp

12emes journees du groupe MODE, Le Havre, 2004. – p.12/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Reformulation (Variable Redefinition)

Dynamic Cut Generation (Separation Sub-Problem)

Dynamic Column Generation (Optimization Sub-Problem)

� � � �� � � � � � � � �� ��

� � �� ��

�� � � ��� ��

�� � �

� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �

Xlp

12emes journees du groupe MODE, Le Havre, 2004. – p.12/47

Decomposition: How

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

Lagrangian relaxation, Lagr. Dual, Subgradient Algorithm

Reformulation (Variable Redefinition)

Dynamic Cut Generation (Separation Sub-Problem)

Dynamic Column Generation (Optimization Sub-Problem)

� � � �� � � � � � � � �� ��

� � �� ��

�� � � ��� ��

�� � �

� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �

� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �

Xlp

12emes journees du groupe MODE, Le Havre, 2004. – p.12/47

Decomposition: Output

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

1. A solution method that exploits our hability to “treat” asubproblem

2. A Dual Bound that is typically better than LP bound

At best, the Lagrangian Dual Bound:While the LP relaxation bound is LP

PSfrag replacements

LP

PSfrag replacements

LP

12emes journees du groupe MODE, Le Havre, 2004. – p.13/47

Decomposition: Output

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

1. A solution method that exploits our hability to “treat” asubproblem

2. A Dual Bound that is typically better than LP bound

At best, the Lagrangian Dual Bound: � � ��� � �� � ��� � � � �� � � � � � �

While the LP relaxation bound is LP

� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �

� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �

PSfrag replacements�

LP

PSfrag replacements

LP

12emes journees du groupe MODE, Le Havre, 2004. – p.13/47

Decomposition: Output

� ��� � � � � �� �

� �� �

difficult

� � �

� � � �

nice

1. A solution method that exploits our hability to “treat” asubproblem

2. A Dual Bound that is typically better than LP bound

At best, the Lagrangian Dual Bound: � � ��� � �� � ��� � � � �� � � � � � �

While the LP relaxation bound is � � ��� � �� � �� � � � �

LP

� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �� � � � � � � � � � � �

� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �� � � � � � � � � � �

PSfrag replacements�

LP

PSfrag replacements

LP

12emes journees du groupe MODE, Le Havre, 2004. – p.13/47

Dantzig-Wolfe Decomposition/ Reformulation

Apply the change of variables:

� � � �� � � � � � � � �� ��

� � �� ��

�� � � ��� ��

�� � �

Then,

� ��� � �� � �� � � � � �

� ��� ��

�� � �� ��

��� � �� � ��

�� � � ��� � �

�� � �

to solve by column generation combined with branch-and-bound:i.e. by branch-and-price

Resoudre le Maitre

Generer une colonne

Resoudre le Maitre

Generer une colonne

Resoudre le Maitre

Generer une colonne

PSfrag replacements

12emes journees du groupe MODE, Le Havre, 2004. – p.14/47

Dantzig-Wolfe Decomposition/ Reformulation

Apply the change of variables:

� � � �� � � � � � � � �� ��

� � �� ��

�� � � ��� ��

�� � �

Then,

� ��� � �� � �� � � � � �

� ��� ��

�� � �� ��

��� � �� � ��

�� � � ��� � �

�� � �

to solve by column generation combined with branch-and-bound:i.e. by branch-and-price

Resoudre le Maitre

Generer une colonne

Resoudre le Maitre

Generer une colonne

Resoudre le Maitre

Generer une colonne

PSfrag replacements

12emes journees du groupe MODE, Le Havre, 2004. – p.14/47

BaPCod : a generic Branch-And-Price Code

The Column Generation approach has proved very successfulin practice

However, restricted to experts due to the difficulty ofimplementing it

‘tool-box” codes : MINTO, ABACUS, BCP, or MAESTRO

Our aim is to develop a ‘black-box” implementation (in thesame way as Cplex or Xpress provide implementation ofBranch-and-Bound)

The user provides a MIP formulation of its problemThe user specifies what constraints make a subproblemThe code reformulates the problem for column generationThe code solves it with a default branch-and-priceimplementation

12emes journees du groupe MODE, Le Havre, 2004. – p.15/47

BaPCod : a generic Branch-And-Price Code

The Column Generation approach has proved very successfulin practice

However, restricted to experts due to the difficulty ofimplementing it

‘tool-box” codes : MINTO, ABACUS, BCP, or MAESTRO

Our aim is to develop a ‘black-box” implementation (in thesame way as Cplex or Xpress provide implementation ofBranch-and-Bound)

The user provides a MIP formulation of its problemThe user specifies what constraints make a subproblemThe code reformulates the problem for column generationThe code solves it with a default branch-and-priceimplementation

12emes journees du groupe MODE, Le Havre, 2004. – p.15/47

BaPCod : a generic Branch-And-Price Code

The Column Generation approach has proved very successfulin practice

However, restricted to experts due to the difficulty ofimplementing it

‘tool-box” codes : MINTO, ABACUS, BCP, or MAESTRO

Our aim is to develop a ‘black-box” implementation (in thesame way as Cplex or Xpress provide implementation ofBranch-and-Bound)

The user provides a MIP formulation of its problemThe user specifies what constraints make a subproblemThe code reformulates the problem for column generationThe code solves it with a default branch-and-priceimplementation

12emes journees du groupe MODE, Le Havre, 2004. – p.15/47

BaPCod : motivations

Practical:

Provides a starting point to try out a column generationapproach.

Allows to test different decompositions: just change thesubproblem definition.

Research Wise:

Demands to generalize ad-hoc features to turn them intogeneric tools: initialization, preprocessing, branching, . . .

Any algorithmic development is made available for allapplications

Permits to test algorithmic features across applications

Future Outcome:

Paves the way for future integration of column generationtechniques in commercial MIP solvers

12emes journees du groupe MODE, Le Havre, 2004. – p.16/47

BaPCod : motivations

Practical:

Provides a starting point to try out a column generationapproach.

Allows to test different decompositions: just change thesubproblem definition.

Research Wise:

Demands to generalize ad-hoc features to turn them intogeneric tools: initialization, preprocessing, branching, . . .

Any algorithmic development is made available for allapplications

Permits to test algorithmic features across applications

Future Outcome:

Paves the way for future integration of column generationtechniques in commercial MIP solvers

12emes journees du groupe MODE, Le Havre, 2004. – p.16/47

BaPCod : motivations

Practical:

Provides a starting point to try out a column generationapproach.

Allows to test different decompositions: just change thesubproblem definition.

Research Wise:

Demands to generalize ad-hoc features to turn them intogeneric tools: initialization, preprocessing, branching, . . .

Any algorithmic development is made available for allapplications

Permits to test algorithmic features across applications

Future Outcome:

Paves the way for future integration of column generationtechniques in commercial MIP solvers

12emes journees du groupe MODE, Le Havre, 2004. – p.16/47

PART 2: Column Generation

Standard Algorithm

Primal/Dual point of view

Stabilization

12emes journees du groupe MODE, Le Havre, 2004. – p.17/47

Dantzig-Wolfe Reformulation: LP relax. and dual

Original P: � ��� � �� � ��� � � � � � �� � � � �

Master IP: � ��� ��

�� � �� ��

�� � �� � ��

�� � � ��� � �

�� � �� �

Relaxed P:

Master LP:

Dual Master:

Lagrangian D: with

12emes journees du groupe MODE, Le Havre, 2004. – p.18/47

Dantzig-Wolfe Reformulation: LP relax. and dual

Original P: � ��� � �� � ��� � � � � � �� � � � �

Master IP: � ��� ��

�� � �� ��

�� � �� � ��

�� � � ��� � �

�� � �� �

Relaxed P: � ��� � �� � ��� � � � �� � � � � � �

Master LP: � ��� ��

�� � �� ��

�� � �� � ��

�� � � ��� � � � � �

Dual Master:

Lagrangian D: with

12emes journees du groupe MODE, Le Havre, 2004. – p.18/47

Dantzig-Wolfe Reformulation: LP relax. and dual

Original P: � ��� � �� � ��� � � � � � �� � � � �

Master IP: � ��� ��

�� � �� ��

�� � �� � ��

�� � � ��� � �

�� � �� �

Relaxed P: � ��� � �� � ��� � � � �� � � � � � �

Master LP: � ��� ��

�� � �� ��

�� � �� �� � � �

��

�� �� � � �

��

��� � � �� �

�Dual Master: � �� � � � �

� �� �

�� � �� � � � � �� � ��

� � � � �

� �� ��� � � � �� � � � � � �� � �

� � � �

� � �� � �

��� � � � �

Lagrangian D: � �� � � � � � � � � � �

with

� � � � � � � ����

� �� �� � �

12emes journees du groupe MODE, Le Havre, 2004. – p.18/47

Standard column generation: primal view

Master Problem

min

� � �� �� � � ��

s.t.

� � �� �� � � �� �

� � ��� � �

�� � �

Restricted Master Problem

(iteration ):

min

s.t.

Subproblem (Oracle) :

If , add to . Otherwise, STOP.

restricted master Lp values

Master LP value iteration

12emes journees du groupe MODE, Le Havre, 2004. – p.19/47

Standard column generation: primal view

Master Problem

min

� � �� �� � � ��

s.t.

� � �� �� � � �� �

� � ��� � �

�� � �

Restricted Master Problem

(iteration

):

� � � �

min

� � � �� �� � � �� � �

s.t.

� � � �� �� � � �� �

� � � �

�� � �

�� � � � �

Subproblem (Oracle) :

If , add to . Otherwise, STOP.

restricted master Lp values

Master LP value iteration

12emes journees du groupe MODE, Le Havre, 2004. – p.19/47

Standard column generation: primal view

Master Problem

min

� � �� �� � � ��

s.t.

� � �� �� � � �� �

� � ��� � �

�� � �

Restricted Master Problem

(iteration

):

� � � �

min

� � � �� �� � � �� � �

s.t.

� � � �� �� � � �� � � � �

� � � �

�� � � � � �

�� � � � �

Subproblem (Oracle) :

If , add to . Otherwise, STOP.

restricted master Lp values

Master LP value iteration

12emes journees du groupe MODE, Le Havre, 2004. – p.19/47

Standard column generation: primal view

Master Problem

min

� � �� �� � � ��

s.t.

� � �� �� � � �� �

� � ��� � �

�� � �

Restricted Master Problem

(iteration

):

� � � �

min

� � � �� �� � � �� � �

s.t.

� � � �� �� � � �� � � � �

� � � �

�� � � � � �

�� � � � �

Subproblem (Oracle) : � ���� � �� � � � � � �� � � � ����� � � � � � � � �� � � � � �

If , add to . Otherwise, STOP.

restricted master Lp values

Master LP value iteration

12emes journees du groupe MODE, Le Havre, 2004. – p.19/47

Standard column generation: primal view

Master Problem

min

� � �� �� � � ��

s.t.

� � �� �� � � �� �

� � ��� � �

�� � �

Restricted Master Problem

(iteration

):

� � � �

min

� � � �� �� � � �� � �

s.t.

� � � �� �� � � �� � � � �

� � � �

�� � � � � �

�� � � � �

Subproblem (Oracle) : � ���� � �� � � � � � �� � � � ����� � � � � � � � ��

If

� � � � � � � �� � � � � � � � � �

, add

� � �

to� �

. Otherwise, STOP.

restricted master Lp values

Master LP value iteration

12emes journees du groupe MODE, Le Havre, 2004. – p.19/47

Standard column generation: primal view

Master Problem

min

� � �� �� � � ��

s.t.

� � �� �� � � �� �

� � ��� � �

�� � �

Restricted Master Problem

(iteration

):

� � � �

min

� � � �� �� � � �� � �

s.t.

� � � �� �� � � �� � � � �

� � � �

�� � � � � �

�� � � � �

Subproblem (Oracle) : � ���� � �� � � � � � �� � � � ����� � � � � � � � ��

If

� � � � � � � �� � � � � � � � � �

, add

� � �

to� �

. Otherwise, STOP.

restricted master Lp values

Master LP value iteration

12emes journees du groupe MODE, Le Havre, 2004. – p.19/47

Standard column generation: dual view

Restricted Master Dual: � �� � � � � � �� � � � � � �� � �

� �� �

� � �� � �

�� ��

� � � � �

Approxim Dual Function :

Subproblem (Oracle) :

uuk

12emes journees du groupe MODE, Le Havre, 2004. – p.20/47

Standard column generation: dual view

Restricted Master Dual: � �� � � � � � �� � � � � � �� � �

� �� �

� � �� � �

�� ��

� � � � � � � � � �

Approxim Dual Function :

� � � � � � � � � ���� � � �

� � � � � �� �

Subproblem (Oracle) :

u

PSfrag replacements�

� ��� ����

12emes journees du groupe MODE, Le Havre, 2004. – p.20/47

Standard column generation: dual view

Restricted Master Dual: � �� � � � � � �� � � � � � �� � �

� �� �

� � �� � �

�� ��

� � � � � � � � � �

Approxim Dual Function :

� � � � � � � � � ���� � � �

� � � � � �� �Subproblem (Oracle) :

� � � � � � � � � � ��� �� � � � � � � � ��

u

PSfrag replacements�

� �� ���

�� ����

12emes journees du groupe MODE, Le Havre, 2004. – p.20/47

Standard column generation: dual view

Restricted Master Dual: � �� � � � � � �� � � � � � �� � �

� �� �

� � �� � �

�� ��

� � � � � � � � � �

Approxim Dual Function :

� � � � � � � � � ���� � � �

� � � � � �� �Subproblem (Oracle) :

� � � � � � � � � � ��� �� � � � � � � � �� � �� � � � �

u

PSfrag replacements�

� ��� ����

�� ���

�� �

� ��

��

��

12emes journees du groupe MODE, Le Havre, 2004. – p.20/47

Standard column generation: dual view

Restricted Master Dual: � �� � � � � � �� � � � � � �� � �

� �� �

� � �� � �

�� ��

� � � � � � � � � �

Approxim Dual Function :

� � � � � � � � � ���� � � �

� � � � � �� �Subproblem (Oracle) :

� � � � � � � � � � ��� �� � � � � � � � �� � �� � � � �

u

PSfrag replacements� � ��

12emes journees du groupe MODE, Le Havre, 2004. – p.20/47

Standard column generation: dual view

Restricted Master Dual: � �� � � � � � �� � � � � � �� � �

� �� �

� � �� � �

�� ��

� � � � � � � � � �

Approxim Dual Function :

� � � � � � � � � ���� � � �

� � � � � �� �Subproblem (Oracle) :

� � � � � � � � � � ��� �� � � � � � � � �� � �� � � � �

u

12emes journees du groupe MODE, Le Havre, 2004. – p.20/47

Standard column generation: dual view

Restricted Master Dual: � �� � � � � � �� � � � � � �� � �

� �� �

� � �� � �

�� ��

� � � � � � � � � �

Approxim Dual Function :

� � � � � � � � � ���� � � �

� � � � � �� �Subproblem (Oracle) :

� � � � � � � � � � ��� �� � � � � � � � �� � �� � � � �

u

PSfrag replacements

� �

� �

Kelley’s cutting plane algorithm 12emes journees du groupe MODE, Le Havre, 2004. – p.20/47

Standard column generation: primal/ dual view

At iteration k, one has

A Primal Bound on the master:

�� � � � � � � � �� � � �

�� � ��A Dual Bound on the master:

� � � � � � � � � �� � � � � � � � �� � � �

u

PSfrag replacements

��

��� �

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

12emes journees du groupe MODE, Le Havre, 2004. – p.21/47

Standard column generation: primal/ dual view

At iteration k, one has

A Primal Bound on the master:

�� � � � � � � � �� � � �

�� � ��A Dual Bound on the master:

� � � � � � � � � �� � � � � � � � �� � � �

u

PSfrag replacements

��

��� �

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

12emes journees du groupe MODE, Le Havre, 2004. – p.21/47

Slow convergence of Kelley’s algorithm

u

PSfrag replacements

��

12emes journees du groupe MODE, Le Havre, 2004. – p.22/47

Slow convergence of Kelley’s algorithm

u

PSfrag replacements

��

12emes journees du groupe MODE, Le Havre, 2004. – p.22/47

Slow convergence of Kelley’s algorithm

u

PSfrag replacements����

12emes journees du groupe MODE, Le Havre, 2004. – p.22/47

Slow convergence of Kelley’s algorithm

u

PSfrag replacements���� � �

12emes journees du groupe MODE, Le Havre, 2004. – p.22/47

Slow convergence of Kelley’s algorithm

u

PSfrag replacements���� � � � �

12emes journees du groupe MODE, Le Havre, 2004. – p.22/47

Slow convergence of Kelley’s algorithm

u

PSfrag replacements

���� � � � � � �

12emes journees du groupe MODE, Le Havre, 2004. – p.22/47

Slow convergence of Kelley’s algorithm

u

PSfrag replacements

���� � � � � � � ��

12emes journees du groupe MODE, Le Havre, 2004. – p.22/47

Slow convergence of Kelley’s algorithm

u

PSfrag replacements

���� � � � � � � ��� �

� �

12emes journees du groupe MODE, Le Havre, 2004. – p.22/47

Instability: observed behaviors

u

PSfrag replacements

���� � � � � � � � �� �

� �

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

PSfrag replacements

Tailing-off

12emes journees du groupe MODE, Le Havre, 2004. – p.23/47

Instability: observed behaviors

uPSfrag replacements

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

PSfrag replacements

Tailing-offHeading-in

12emes journees du groupe MODE, Le Havre, 2004. – p.23/47

Instability: observed behaviors

uPSfrag replacements

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

PSfrag replacements

Tailing-offHeading-in

Degeneracy

12emes journees du groupe MODE, Le Havre, 2004. – p.23/47

Instability: observed behaviors

u

u0 u1

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

PSfrag replacements

Tailing-offHeading-in

Degeneracy

Bang-Bang Behavior

12emes journees du groupe MODE, Le Havre, 2004. – p.23/47

Instability: observed behaviors

u

u0 u2 u1

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

PSfrag replacements

Tailing-offHeading-in

Degeneracy

Bang-Bang Behavior

12emes journees du groupe MODE, Le Havre, 2004. – p.23/47

Instability: observed behaviors

u

u0 u2 u3 u1

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

PSfrag replacements

Tailing-offHeading-in

Degeneracy

Bang-Bang Behavior

12emes journees du groupe MODE, Le Havre, 2004. – p.23/47

Instability: observed behaviors

u

u0 u2 u4 u3 u1

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

PSfrag replacements

Tailing-offHeading-in

Degeneracy

Bang-Bang Behavior

12emes journees du groupe MODE, Le Havre, 2004. – p.23/47

Instability: observed behaviors

u

u0 u2 u5 u4 u3 u1

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

PSfrag replacements

Tailing-offHeading-in

Degeneracy

Bang-Bang Behavior

12emes journees du groupe MODE, Le Havre, 2004. – p.23/47

Instability: observed behaviors

u

u0 u2 u5 u4 u3 u1

restricted master Lp values

intermediate Lagrangian bounds

Master LP value iteration

PSfrag replacementsTailing-offHeading-in

Degeneracy

Jumpy Behavior

Bang-Bang Behavior

12emes journees du groupe MODE, Le Havre, 2004. – p.23/47

Stabilization Methods -

penalizing distance from a stability center

���

��� � best dual bound

(box step)R.E.Martsen, W.W.Hogan and J.W.Blankenship, 1975

(1 breakpoint)S.Kim, K.N.Chang and J.Y.Lee, 1995

penalization outsideboxstep (3 breakpoints)O.du Merle, D.Villeneuve, J.Desrosiers and P.Hansen, 1999

= penalization outside 2 boxsteps(4 breakpoints)H.Ben-Amor and J.Desrosiers, 2003

BundleC. Lemarechal and C. Sagastizabal, 1997

12emes journees du groupe MODE, Le Havre, 2004. – p.24/47

Stabilization Methods -

��� ��� � �

� � � � � �

� � � � �

penalizing distance from a stability center

���

(box step)R.E.Martsen, W.W.Hogan and J.W.Blankenship, 1975

(1 breakpoint)S.Kim, K.N.Chang and J.Y.Lee, 1995

penalization outsideboxstep (3 breakpoints)O.du Merle, D.Villeneuve, J.Desrosiers and P.Hansen, 1999

= penalization outside 2 boxsteps(4 breakpoints)H.Ben-Amor and J.Desrosiers, 2003

BundleC. Lemarechal and C. Sagastizabal, 1997

12emes journees du groupe MODE, Le Havre, 2004. – p.24/47

Stabilization Methods -

��� ��� � �

� � � � � �

� � � � �

penalizing distance from a stability center

���

� � � � � � � � � �� � � � � � � � � � �

(box step)R.E.Martsen, W.W.Hogan and J.W.Blankenship, 1975

(1 breakpoint)S.Kim, K.N.Chang and J.Y.Lee, 1995

penalization outsideboxstep (3 breakpoints)O.du Merle, D.Villeneuve, J.Desrosiers and P.Hansen, 1999

= penalization outside 2 boxsteps(4 breakpoints)H.Ben-Amor and J.Desrosiers, 2003

BundleC. Lemarechal and C. Sagastizabal, 1997

u

PSfrag replacements

� ��� ��� � �

�� ���� �

� �

12emes journees du groupe MODE, Le Havre, 2004. – p.24/47

Stabilization Methods -

��� ��� � �

� � � � � �

� � � � �

penalizing distance from a stability center

���

� � � � � � � � � �� � � � � � � � � � �

(box step)R.E.Martsen, W.W.Hogan and J.W.Blankenship, 1975

� � � � � � � � � � � � � � � � � (1 breakpoint)S.Kim, K.N.Chang and J.Y.Lee, 1995

penalization outsideboxstep (3 breakpoints)O.du Merle, D.Villeneuve, J.Desrosiers and P.Hansen, 1999

= penalization outside 2 boxsteps(4 breakpoints)H.Ben-Amor and J.Desrosiers, 2003

BundleC. Lemarechal and C. Sagastizabal, 1997

u

PSfrag replacements

� ��� ��� � �

�� ���� �

� �

12emes journees du groupe MODE, Le Havre, 2004. – p.24/47

Stabilization Methods -

��� ��� � �

� � � � � �

� � � � �

penalizing distance from a stability center

���

� � � � � � � � � �� � � � � � � � � � �

(box step)R.E.Martsen, W.W.Hogan and J.W.Blankenship, 1975

� � � � � � � � � � � � � � � � � (1 breakpoint)S.Kim, K.N.Chang and J.Y.Lee, 1995

� � � � � � � � � � � � � � � � � �

penalization outsideboxstep (3 breakpoints)O.du Merle, D.Villeneuve, J.Desrosiers and P.Hansen, 1999

= penalization outside 2 boxsteps(4 breakpoints)H.Ben-Amor and J.Desrosiers, 2003

BundleC. Lemarechal and C. Sagastizabal, 1997

u

PSfrag replacements

� ��� ��� � �

�� ���� �

� �

12emes journees du groupe MODE, Le Havre, 2004. – p.24/47

Stabilization Methods -

��� ��� � �

� � � � � �

� � � � �

penalizing distance from a stability center

���

� � � � � � � � � �� � � � � � � � � � �

(box step)R.E.Martsen, W.W.Hogan and J.W.Blankenship, 1975

� � � � � � � � � � � � � � � � � (1 breakpoint)S.Kim, K.N.Chang and J.Y.Lee, 1995

� � � � � � � � � � � � � � � � � �

penalization outsideboxstep (3 breakpoints)O.du Merle, D.Villeneuve, J.Desrosiers and P.Hansen, 1999

� � � � � � �

= penalization outside 2 boxsteps(4 breakpoints)H.Ben-Amor and J.Desrosiers, 2003

BundleC. Lemarechal and C. Sagastizabal, 1997

u

PSfrag replacements

� ��� ��� � �

�� ���� �

� �

12emes journees du groupe MODE, Le Havre, 2004. – p.24/47

Stabilization Methods -

��� ��� � �

� � � � � �

� � � � �

penalizing distance from a stability center

���

� � � � � � � � � �� � � � � � � � � � �

(box step)R.E.Martsen, W.W.Hogan and J.W.Blankenship, 1975

� � � � � � � � � � � � � � � � � (1 breakpoint)S.Kim, K.N.Chang and J.Y.Lee, 1995

� � � � � � � � � � � � � � � � � �

penalization outsideboxstep (3 breakpoints)O.du Merle, D.Villeneuve, J.Desrosiers and P.Hansen, 1999

� � � � � � �

= penalization outside 2 boxsteps(4 breakpoints)H.Ben-Amor and J.Desrosiers, 2003

BundleC. Lemarechal and C. Sagastizabal, 1997

u

PSfrag replacements

� ��� ��� � �

�� ���� �

� �

� As

� � � � � � �is a concave and piecewise linear function,we can still use LP solvers

12emes journees du groupe MODE, Le Havre, 2004. – p.24/47

Stabilization Methods -

��� ��� � �

� � � � � �

� � � � �

penalizing distance from a stability center

���

� � � � � � � � � �� � � � � � � � � � �

(box step)R.E.Martsen, W.W.Hogan and J.W.Blankenship, 1975

� � � � � � � � � � � � � � � � � (1 breakpoint)S.Kim, K.N.Chang and J.Y.Lee, 1995

� � � � � � � � � � � � � � � � � �

penalization outsideboxstep (3 breakpoints)O.du Merle, D.Villeneuve, J.Desrosiers and P.Hansen, 1999

� � � � � � �

= penalization outside 2 boxsteps(4 breakpoints)H.Ben-Amor and J.Desrosiers, 2003

� � � � � � � � � �� � � � � � � � � � � BundleC. Lemarechal and C. Sagastizabal, 1997

u

PSfrag replacements

� ��� ��� � �

�� ���� �

� �

12emes journees du groupe MODE, Le Havre, 2004. – p.24/47

Stabilization Methods -

��� ��� � �

� � � � � �

� � � � �

penalizing distance from a stability center

���

� � � � � � � � � �� � � � � � � � � � �

(box step)R.E.Martsen, W.W.Hogan and J.W.Blankenship, 1975

� � � � � � � � � � � � � � � � � (1 breakpoint)S.Kim, K.N.Chang and J.Y.Lee, 1995

� � � � � � � � � � � � � � � � � �

penalization outsideboxstep (3 breakpoints)O.du Merle, D.Villeneuve, J.Desrosiers and P.Hansen, 1999

� � � � � � �

= penalization outside 2 boxsteps(4 breakpoints)H.Ben-Amor and J.Desrosiers, 2003

� � � � � � � � � �� � � � � � � � � � � BundleC. Lemarechal and C. Sagastizabal, 1997

u

PSfrag replacements

� ��� ��� � �

�� ���� �

� �

� As� � � � � � �

is a quadratic concave function,we must now use Quadratic solvers K.C.Kiwiel, 1989, 1994, A.Frangioni, 1996

12emes journees du groupe MODE, Le Havre, 2004. – p.24/47

Stabilization Methods

smoothing dual value : � � � � � ��� � � � � � �� � � � � � � �P.Wentges, 1997

Using interior-point-like technique to generate dual solution

Kelley solved by interior point methodL-M Rousseau, M.Gendreau and D.Feillet, 2003

Analytic Center Cutting-Plane Method (ACCPM)

log log

J.L. Goffin, A.Haurie and J.Ph. Vial, 1992

Kelley

analytic center

PSfrag replacements

12emes journees du groupe MODE, Le Havre, 2004. – p.25/47

Stabilization Methods

smoothing dual value : � � � � � ��� � � � � � �� � � � � � � �P.Wentges, 1997

Using interior-point-like technique to generate dual solution

Kelley solved by interior point methodL-M Rousseau, M.Gendreau and D.Feillet, 2003

Analytic Center Cutting-Plane Method (ACCPM)

log log

J.L. Goffin, A.Haurie and J.Ph. Vial, 1992

Kelley

analytic center

PSfrag replacements

12emes journees du groupe MODE, Le Havre, 2004. – p.25/47

Stabilization Methods

smoothing dual value : � � � � � ��� � � � � � �� � � � � � � �P.Wentges, 1997

Using interior-point-like technique to generate dual solution

Kelley solved by interior point methodL-M Rousseau, M.Gendreau and D.Feillet, 2003

Analytic Center Cutting-Plane Method (ACCPM)

��� � � � � �� � �

log

��� � � � � � �� � � � � �

log

�� � � � � � � � � � �

J.L. Goffin, A.Haurie and J.Ph. Vial, 1992

Kelley

analytic center

PSfrag replacements�� � �

��

12emes journees du groupe MODE, Le Havre, 2004. – p.25/47

Bi-Dual: Fenchel duality

� �� � � � � � � � ��� � � �� � � �� � � � �� �� � ��

� �� � � � � � � � � � � � � � � � � �

12emes journees du groupe MODE, Le Havre, 2004. – p.26/47

Bi-Dual: Fenchel duality

� � � � � � � � � � ��� � � �� � � �� � � � � � �� � ��

� � � � � � � � � � � � � � � � � � ��� � � � � � �� � �� �� � �

� � �� � � � � � � �� � � � � �� �

12emes journees du groupe MODE, Le Havre, 2004. – p.26/47

Bi-Dual: Fenchel duality

� � � � � � � � � � ��� � � �� � � �� � � � � � �� � ��

� � � � � � � � � � � � � � � � � � ��� � � � � � �� � �� �� � �

� � �� � � � � � � �� � � � � �� �PSfrag replacements

� ��

��

� ���

� � �

�� � �� ��

�� �� � � � � ��� � � �

��� �

� � � � � �� � �

� � �

�� � �� � � � � � � � � � � � �� � � � �

� � � �� � � � � � � �� � � � �

� � �

�� � � �

�� � � �

12emes journees du groupe MODE, Le Havre, 2004. – p.26/47

PART 3: Numerical Comparison

12emes journees du groupe MODE, Le Havre, 2004. – p.27/47

Tested variants

1. “Poor” initializationKelley initialized with

artificial columnBundle initialized with � � �

2. “Rich” initialization: heuristic

� �

Kelley initialized with � artificial columns of cost

� �

Bundle initialized with � � � � �

3. Primal / Dual approach :Kelley (for primal bounds)

“rich” bundle (for dual bounds)

12emes journees du groupe MODE, Le Havre, 2004. – p.28/47

Traveling Salesman Problems (TSP)

��

��������������������������������������������������������������

� � � � � � � � � �

Instances from TSPLIB

12emes journees du groupe MODE, Le Havre, 2004. – p.29/47

TSP : bays29 : primal and dual bounds

43 iterations

0 100 200 300 400 500 600 700 800 900 1000

0

1820

3640

5460

7280

9100

10920

12740

14560

16380

18200

Dual bound with BundlePrimal bound with Bundle

Primal bound with Stabilized KelleyDual bound with Stabilized Kelley

744 iterations

419 iterations

43 iterations

0 100 200 300 400 500 600 700 800 900 1000

0

1820

3640

5460

7280

9100

10920

12740

14560

16380

18200

Dual bound with KelleyPrimal bound with KelleyDual bound with Stabilized KelleyPrimal bound with Stabilized KelleyDual bound with BundlePrimal bound with Bundle

12emes journees du groupe MODE, Le Havre, 2004. – p.30/47

TSP : bays29 : primal and dual bounds

419 iterations

43 iterations

0 100 200 300 400 500 600 700 800 900 1000

0

1820

3640

5460

7280

9100

10920

12740

14560

16380

18200

Dual bound with Stabilized KelleyPrimal bound with Stabilized KelleyDual bound with BundlePrimal bound with Bundle

744 iterations

419 iterations

43 iterations

0 100 200 300 400 500 600 700 800 900 1000

0

1820

3640

5460

7280

9100

10920

12740

14560

16380

18200

Dual bound with KelleyPrimal bound with KelleyDual bound with Stabilized KelleyPrimal bound with Stabilized KelleyDual bound with BundlePrimal bound with Bundle

12emes journees du groupe MODE, Le Havre, 2004. – p.30/47

TSP : bays29 : primal and dual bounds

744 iterations

419 iterations

43 iterations

0 100 200 300 400 500 600 700 800 900 1000

0

1820

3640

5460

7280

9100

10920

12740

14560

16380

18200

Dual bound with KelleyPrimal bound with KelleyDual bound with Stabilized KelleyPrimal bound with Stabilized KelleyDual bound with BundlePrimal bound with Bundle

12emes journees du groupe MODE, Le Havre, 2004. – p.30/47

TSP : eil51 : primal and dual bounds

92 iterations

0 100 200 300 400 500 600 700 800 900 1000

0

84

169

253

338

422

506

591

675

760

844

Dual bound with KelleyPrimal bound with KelleyDual bound with Stabilized KelleyPrimal bound with Stabilized KelleyDual bound with BundlePrimal bound with Bundle

12emes journees du groupe MODE, Le Havre, 2004. – p.31/47

TSP : eil76 : primal and dual bounds

153 iterations

0 100 200 300 400 500 600 700 800 900 1000

0

107

215

322

430

537

644

752

859

967

1074

Dual bound with KelleyPrimal bound with KelleyDual bound with Stabilized KelleyPrimal bound with Stabilized Kelley

Primal bound with BundleDual bound with Bundle

12emes journees du groupe MODE, Le Havre, 2004. – p.32/47

TSP : pr76 : primal and dual bounds

Dual bound with KelleyPrimal bound with KelleyDual bound with Stabilized KelleyPrimal bound with Stabilized KelleyDual bound with BundlePrimal bound with Bundle

155 iterations

0 100 200 300 400 500 600 700 800 900 1000

0

21024

42048

63072

84096

105120

126144

147168

168192

189216

210240

12emes journees du groupe MODE, Le Havre, 2004. – p.33/47

TSP : gr120 : primal and dual bounds

210 iterations

0 100 200 300 400 500 600 700 800 900 1000

0

321

642

964

1285

1606

1927

2248

2570

2891

3212

Dual bound with KelleyPrimal bound with KelleyDual bound with Stabilized KelleyPrimal bound with Stabilized KelleyDual bound with BundlePrimal bound with Bundle

12emes journees du groupe MODE, Le Havre, 2004. – p.34/47

pr76 : first 1-trees with Kelley

12emes journees du groupe MODE, Le Havre, 2004. – p.35/47

pr76 : first 1-trees with Stabilized Kelley

12emes journees du groupe MODE, Le Havre, 2004. – p.36/47

pr76 : first 1-trees with Bundle

12emes journees du groupe MODE, Le Havre, 2004. – p.37/47

Capacitated Vehicle Routing Problem (CVRP)

Instances from CVRPLIB

12emes journees du groupe MODE, Le Havre, 2004. – p.38/47

CVRP : Comparative results

Counters Timers (ticks)

Problem Method Iter Col Oracle Master total

n22-k8 kelley poor 53 53 277 12 2s99t

n22-k8 kelley rich 52 35 323 8 3s36t

n22-k8 bundle rich 42 32 483 17 5s08t

n14-k2 kelley poor 54 54 26317 5 4m23s

n14-k2 kelley rich 44 43 30732 3 5m07s

n14-k2 bundle rich 16 14 180509 6 30m05s

12emes journees du groupe MODE, Le Havre, 2004. – p.39/47

Cutting Stock Problem

s1 s2 s3 s4

� � � number of rolls

��

� ��� � � �

� � � �

� �� ��

� �� � � �

� � �

� �

� ��� waste�

��

� ��� �

� � � � �� � � ��

�� � � � � �

� �� � �

� �� � � �

� � �

� �

12emes journees du groupe MODE, Le Havre, 2004. – p.40/47

CSP number of rolls: Comparative results

average on 10 or 20 instancesCounters Timers (ticks)

Problem Method Iter Col Oracle Master total

realDat20 kelley poor 44 45 54 4 0s65t

realDat20 bundle poor 90 52 772 32 8s17t

realDat20 kelley rich 32 32 434 3 4s42t

realDat20 bundle rich 51 38 1149 20 11s76t

realDat20 bundle + Kelley 39 33 888 14 9s9t

50b100 kelley poor 228 228 612 51 7s4t

50b100 bundle poor 257 190 1633 577 22s56t

50b100 kelley rich 138 138 521 33 5s82t

50b100 bundle rich 145 123 1717 241 19s87t

50b100 bundle + Kelley 124 115 1263 129 14s22t

12emes journees du groupe MODE, Le Havre, 2004. – p.41/47

CSP number of rolls: primal and dual bounds

0 12 24 36 48 60 72 84 96 108 120

0

5

10

15

20

25

30

35

40

45

50

Primal bound with Stabilized KelleyDual bound with Stabilized KelleyPrimal bound with Kelley (kelley and bundle)Dual bound with Bundle (kelley and bundle)

12emes journees du groupe MODE, Le Havre, 2004. – p.42/47

CSP Waste: Comparative results

average on 10 or 20 instancesCounters Timers (ticks)

Problem Method Iter Col Oracle Master total

realDat20 kelley poor 50 50 116 74 1s33t

realDat20 kelley rich 47 47 146 8 1s66t

realDat20 bundle rich 71 50 1250 38 13s1t

50b100 kelley poor 146 144 794 40 8s83t

50b100 kelley rich 177 176 700 70 8s24t

50b100 bundle rich 205 149 1815 548 24s18t

12emes journees du groupe MODE, Le Havre, 2004. – p.43/47

CSP Waste: primal and dual bounds

Primal bound with Stabilized KelleyDual bound with Stabilized KelleyPrimal bound with Kelley (kelley and bundle)Dual bound with Bundle (kelley and bundle)

0 7 14 21 28 35 42 49 56 63 70

−5

−4

−3

−2

−1

0

1

2

3

4

5

12emes journees du groupe MODE, Le Havre, 2004. – p.44/47

Multi-Item Lot-Sizing : Comparative results

Machine

Item 2

Item 1

Periods 1 to 5

PSfrag replacements

��

��

������

������

������

������

average on 10 instances Decomposition in SILSCounters Timers (ticks)

Problem Method Iter SP Col Oracle Master total

i20-t60 kelley 8 164 117 55 4 4s79t

i20-t60 bundle 66 1326 207 455 92 18s41t

12emes journees du groupe MODE, Le Havre, 2004. – p.45/47

Observations

(based on preliminary results)

Bundle takes far fewer iterations for some applications (likeTSP), while not much is to win (compared to kelley) in otherapplications.

? Characterization ?

Stabilization may imply harder oracles. Hence, there is a timetradeoff.

Kelley finds primal feasible solution earlier.

Kelley accepts inexact oracles.

12emes journees du groupe MODE, Le Havre, 2004. – p.46/47

Example: Multi-Item Lot-Sizing

R

Machine

Item 2

Item 1

Periods 1 to 5PSfrag replacements

��

��

������

������

������

������

12emes journees du groupe MODE, Le Havre, 2004. – p.47/47

Example: Multi-Item Lot-Sizing

R

Machine

Item 2

Item 1

Periods 1 to 5PSfrag replacements

��

��

������

������

������

������

� � �

� �� � �� �

12emes journees du groupe MODE, Le Havre, 2004. – p.47/47

Example: Multi-Item Lot-Sizing

R

Machine

Item 2

Item 1

Periods 1 to 5PSfrag replacements

��

��

������

������

������

������

� � �

� �� � �� �

� � � �

� �� � �

12emes journees du groupe MODE, Le Havre, 2004. – p.47/47

Example: Multi-Item Lot-Sizing

R

Machine

Item 2

Item 1

Periods 1 to 5PSfrag replacements

��

��

������

������

������

������

� � �

� �� � �� �

� � � �

� �� � �

� �� � �

� �� �� �

� � ��

12emes journees du groupe MODE, Le Havre, 2004. – p.47/47