Transcript From PW and MIP to PP by MIP

Y. Pochet, Lhoist Group
IP at CORE
May 27-29, 2009
From
PW and MIP
to
PP by MIP
From
Production Waste and Milling Intermediate Products
To
Production Performance by Milling Inequality Polyhedron
Outline
• Supply Chain Network at Lhoist
• Lime Basics
• Production Waste Constraint and Model for the Milling
Process
• Milling Inequality Polyhedron
• Improved Production Performance using the Milling Inequality
Polyhedron
2
Lhoist Group
Lhoist is a privately held lime company
•Headquarters in Limelette, Belgium, Europe
Lhoist is the leading lime manufacturer in the world with over 70 operations in:
•Belgium, France, Germany, Denmark,
•Poland, Czech Republic, England, Spain, Portugal, North- and Central America
•Brazil
Supply Chain Network Optimization at Lhoist
Lhoist Group is using an APS (Advanced Planning Software) as part of its DSS
(Decision Support System) for its strategic and tactical “supply chain network
optimizations”.
Development started in 1991, research project Lhoist (P. Sevrin) – UCL (Y. Pochet)
Specificity: divergent product structure with linked co-products (grain size, physical
and chemical quality, variable recipes,…)
 difficult flow balance constraints within the plants.
The system and the optimization approach have been used extensively within
Lhoist Group for many strategic studies. The system will never be a “decision
system” and will remain a support to challenge creativity and entrepreneurship.
3
Why Supply Chain Network Optimization?
Impact on EBITDA
&
ROCE
Operational
buy
Tactical
Material planning
make
Scheduling
Master Planning
move
Transportation Scheduling
Transport & Resource
Planning
store
Inventory Management
Distribution Planning
sell
partner
Strategic
Supply
Chain
Network
Optimisation
Forecasting & Order Promising
Collaborative Planning, Forecasting & Replenishment
4
European Lime Production & Delivery
SC Network : From the Quarry to the Customer
5
Lime Production: Plant Mass Flows
6
Outline
• Supply Chain Network at Lhoist
• Lime Basics
• Production Waste Constraint and Model for the Milling
Process
• Milling Inequality Polyhedron
• Improved Production Performance using the Milling
Inequality Polyhedron
7
Outline
• Supply Chain Network at Lhoist
• Lime Basics
• Production Waste Constraint and Model for the Milling
Process
• Milling Inequality Polyhedron
• Improved Production Performance using the Milling
Inequality Polyhedron
• As Karen would say:
I don’t have the foggiest idea what this
is about…
Let’s try again!
8
This is not only about science
This is about something else …
9
Y. Pochet, Lhoist Group
IP at CORE
May 27-29, 2009
From
PW and MIP
to
PP by MIP
From
(Pochet-) Wolsey
and
Mixed Integer Programming
To
Production Planning
by
Mixed Integer Programming
The Goal: Thank you Laurence
for your exceptional guidance!
• Laurence’s PhD Students
(+ many others, sorry ! )
 Work inspired by Laurence
 Constant drive to develop his students
 Fascination for the Lot-Sizing world
• Area/Era 1: The Happy few
or PP and MIP
 Single item planning models
 Specific Reformulations (cutting planes, extended,…)
• Area/Era 2: The Happy many or PP by MIP
 Multi item production planning models
 Optimization algorithms & Systems
 Generalizations to MIPs & Generic reformulations
• Area 3: The Happy all or MIP/IP





Facility Location
Scheduling and Constraint Programming
Partitioning Problems
Graphs with Bounded Decomposability ; Flows
Markov and Groebner Bases
11
Laurence’s PhD Students
1. Y. Pochet, Lot-Sizing Problems: Reformulations and Cutting Plane
Algorithms (1987)
2. C. Bousba, Planification des Réseaux Electriques de Distribution à
Basse Tension: une Approche par la Programmation Mathématique
(1989)
3. J.P. de Sousa, Time Indexed Formulations of Non-Preemptive
Single-Machine Scheduling Problems (1989)
4. K. Aardal, On the Solution of One and Two-Level Capacitated
Facility Location Problems by the Cutting Plane Approach (1992)
5. E-H Aghezzaf, Optimal Constrained Rooted Subtrees and
Partitioning Problems on Tree Graphs (1992)
6. C. de Souza, The Graph Equipartition Problem: Optimal Solutions,
Extensions and Applications (1993)
7. M. Schaffers, On Links between Graphs with Bounded
Decomposability, Existence of Efficient Algorithms, and Existence
of Polyhedral Characterizations (1994)
8. F. Vanderbeck, Decomposition and Column Generation for Integer
Programs (1994)
9. M. Constantino, A Polyhedral Approach to Production Planning
Models: Start-Up Costs and Times, Upper and Lower Bounds on
Production (1995)
12
Laurence’s PhD Students
10. H. Marchand, A Polyhedral Study of the Mixed Knapsack Set and its Use
to Solve Mixed Integer Programs (1998)
11. G. Belvaux, Modelling and Solving Lot-Sizing Problems by Mixed Integer
Programming (1999)
12. C. Cordier, Development and Experimentation with a Branch and Cut
System for Mixed Integer Programming (1999)
13. M. Loparic, Stronger Mixed 0-1 Models for Lot-Sizing Problems (2001)
14. F. Ortega, Formulations and Algorithms for Fixed Charge Networks and
Lot-Sizing Problems (2001)
15. M. Van Vyve, A Solution Approach of Production Planning Problems based
on Compact Formulations for Single-Item Lot-Sizing Models (2003)
16. Q. Louveaux, Exploring Structure and Reformulations in Different Integer
Programming Algorithms(2004)
17. J-F. Macq, Optimization of Multimedia Flows over Data Networks (2005)
18. R. Sadykov, Integer Programming-based Decomposition Approaches
for Solving Machine Scheduling Problems (2006)
19. P. Malkin, Computing Markov bases, Groebner bases and extreme rays
(2007)
13
Area 1: Lot Sizing Models LS-C
• Single Item : LS-U ; LS-C ; LS-CC (Wagner-Whitin costs WW ; Discrete Prod. DLS)
Variants :
Backlogging
[LS,WW,DLS]1 - [U,C,CC]1
/B
Start-Up Costs
[LS,WW,DLS]1 - [U,C,CC]1
/ SC
Start-Up Times
[LS,WW,DLS]1 - [U,C,CC]1
/ ST
Sales (profit max) [LS,WW,DLS]1 - [U,C,CC]1
/ SL
1
1
Safety Stocks
[LS,WW,DLS] - [U,C,CC]
/ SS
1
1
Lower Bounds
[LS,WW,DLS] - [U,C,CC]
/ LB
Research Stream on Algorithms ; Valid Inequalities ; Extended Reformulations
14
A long story … LAW’s PhD Di-graph
V I Fixed Charge Problems
( SNF) [MP, ’85]
Seminal Contributions
APPLICATION

THEORY
COMPUTATION
Padberg, Van Roy, Wolsey
LS-U : Convex Hull
[MP, ’84]
V I Uncap. Fixed Charge
Networks [ORL, ’85]
Mixed 0-1 Automatic
Reformulation [OR, ’87]
Barany, Van Roy, Wolsey
Barany, Van Roy, Wolsey
Van Roy, Wolsey
Cap. Facility Loc.:
[MOR, ’95]
LS-B : [MP, ’88]
ML-S : [??, ’87]
LS-C : [ORL, ’88]
P, Wolsey
P
P, Wolsey
Aardal, P, Wolsey
LS-C/ SC : [MP, ’96]
Constantino
LS-U/ concave
[DAM, ’94]
Aghezzaf,
Wolsey
LS-U / # set-ups :
[ORL, ’92]
LS-CC : [MOR, ’93]
P, Wolsey
Aghezzaf, Wolsey
LS-C/ ST : [MS, ’98]
Vanderbeck
WW-U,CC,B,SC : [MP, ’94]
IP Col. Generation : [ORL, ’96]
P, Wolsey
Vanderbeck, Wolsey
15
LAW’s PhD Di-graph
APPLICATION

THEORY
LS-U / LS-CC
WW-U,CC,B,SC
Mixing MIR ineq:
[MP, ’01]
Günlük, P
Mixing Sets :
Van Vyve [MOR,’05]
Conforti, Wolsey
Miller, Wolsey
WW-CC/ LB :
Constantino [MOR, ’98]
Van Vyve [’03]
WW-U/ B,SC : [ORL, ’99]
Agra, Constantino
LS-U/SL, SS : [MP, ’01]
COMPUTATION
0-1 continuous knapsack :
[MP, ’99]
BC-PROD : [MS, ’00]
Marchand, Wolsey
Belvaux, Wolsey
C-MIR ineq. for MIPs :
[OR, ’01]
BC-OPT : [MP, ’99]
Marchand, Wolsey
Cordier, Wolsey
Loparic, P, Wolsey
LS / fixed charge networks :
[DO, ’04]
Ortega, Van Vyve
LS-CC-B : Reform. [MP, ’06]
Algor. [MOR, ’07]
Van Vyve
LS-C & Dynamic knapsack
sets : [MP, ’03]
Loparic, Marchand,
Wolsey
Lifting, MIR, SNF : [4OR, ’03]
LS-LIB : [Springer, ’08]
Louveaux, Wolsey
P, Van Vyve, Wolsey
16
Thank you so much Laurence for your
• Patience (personal comment)
• Permanent challenging mindset: Asking (us) the right - but
tough - questions at the right time
• Constant Drive
• Intuition and deep knowledge of the field
• Continuous source of inspiration and intellectual motivation
• Guidance
• Friendship
17
NIPAG
(3.5
tons/hour)
PULSAG
(10 tons/hour)
NIPAG
Buffer
Dry Material (70 Tons
Addition
200 Tons
MAx)
PULSAG
Buffer
150 tons
7 FUTUR
8 EURO
PULSAR
3 JAPAN
PULSAR
Yves, Choaib, Jorge, Karen,
El Houssaine, Cid, Michel,
White
Buffer
Storage
50-60 Tons/Hour
15 % FUTUR
10 % PULSAR
Brand Change-over 15 Min.
François, Miguel, Hugues,
Gaëtan, Cécile, Marko,
Matrix
Pulsar/Alpine
/Futur
(50 Tons)
Matrix Buffer
Japanese
(80 Tons)
Re-Blend
Storage
Francisco dit Pancho,
Mathieu, Quentin,
Jean-François, Ruslan, Peter.
Colouring Unit
(16 Tons/hour)
GREEN
Buffer
Storage
18