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
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 Stabilized Kelley
12emes journees du groupe MODE, Le Havre, 2004. – p.36/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