La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Integrating concepts from constraint programming and operations research algorithms [Elektronische Ressource] / von Torsten Fahle

264 pages
Integrating Concepts fromConstraint Programming andOperations Research AlgorithmsDissertationvonTorsten FahleSchriftliche Arbeit zur Erlangung des Gradeseines Doktors der NaturwissenschaftenFakultät für Elektrotechnik, Informatik und Mathematikder Universität Paderborn.Paderborn, Dezember 2002When you have eliminated the impossible,whatever remains, however improbable, must be the truth.Sir Arthur Conan Doyle (1859–1930)Sherlock Holmes to Dr. Watsonin The Sign of Four [68].But we all know the world is nonlinear.Harold Hotelling, (1910–1975)to George Dantzig, 1947 [59].1Jede Lösung eines Problems ist ein neues Problem.Johann Wolfgang von Goethe (1749–1832)to chancellor von Müller, 1821 [95].1Every solution of a problem is a new problem. (non-authorized translation)iiiivAcknowledgmentResearch is seldom a one-person project and many individuals have contributed to the resultspresented in this thesis. The first to mention here is my supervisor Prof. Dr. Burkhard Monienfor his support during the last few years and for providing an excellent working environmentin his group.2I am very indebted to my colleagues in the research group and in the PC for provid-ing a good working atmosphere. I would especially like to thank Rainer Feldmann, SilviaGötz, Sven Grothklags, Georg Kliewer, Jürgen Schulze, Norbert Sensen, Ulf-Peter Schroederand Meinolf Sellmann for interesting discussions on optimization topics.
Voir plus Voir moins

Integrating Concepts from
Constraint Programming and
Operations Research Algorithms
Dissertation
von
Torsten Fahle
Schriftliche Arbeit zur Erlangung des Grades
eines Doktors der Naturwissenschaften
Fakultät für Elektrotechnik, Informatik und Mathematik
der Universität Paderborn.
Paderborn, Dezember 2002When you have eliminated the impossible,
whatever remains, however improbable, must be the truth.
Sir Arthur Conan Doyle (1859–1930)
Sherlock Holmes to Dr. Watson
in The Sign of Four [68].
But we all know the world is nonlinear.
Harold Hotelling, (1910–1975)
to George Dantzig, 1947 [59].
1Jede Lösung eines Problems ist ein neues Problem.
Johann Wolfgang von Goethe (1749–1832)
to chancellor von Müller, 1821 [95].
1Every solution of a problem is a new problem. (non-authorized translation)
iiiivAcknowledgment
Research is seldom a one-person project and many individuals have contributed to the results
presented in this thesis. The first to mention here is my supervisor Prof. Dr. Burkhard Monien
for his support during the last few years and for providing an excellent working environment
in his group.
2I am very indebted to my colleagues in the research group and in the PC for provid-
ing a good working atmosphere. I would especially like to thank Rainer Feldmann, Silvia
Götz, Sven Grothklags, Georg Kliewer, Jürgen Schulze, Norbert Sensen, Ulf-Peter Schroeder
and Meinolf Sellmann for interesting discussions on optimization topics. Uli Ahlers, Sven
Grothklags, Georg Kliewer, Tomas Plachetka, Stefan Schamberger, Norbert Sensen, Thomas
Thissen and the LINUX-Gurus could always help me with the C++ standard, CPLEX’s “spe-
cial features”, shell-programming, mysterious bugs in the code or extra hard- and software
requirements.
2 3Parts of this thesis were supported by the EU-Esprit projects PARALOR and ALCOM-FT
4and by the BMBF project PARPAP . Michael Laska’s management and administration of these
projects was very much appreciated and helped us to concentrate on the research in question.
Within the projects I had the pleasure of working in co-operation with other researchers. I
would like to say: Merci bien, Ulrich, Mange tak, Stefan, Niklas and Bo,Eνχαστ ωπ´ oλν´,
Takis and Kyriakos, Danke schön, Stefan, Sven, Georg, Stefan, Jürgen and Meinolf for the
fruitful collaboration which resulted in some joint papers.
Geraldine Brehony found all those misspellings that only a non-native writer could make
— . In addition, Ruth Dietzel, Sandra Feisel, Sven Grothklags,
Georg Kliewer and Manuel Rode read and commented on individual chapters — thanks a lot!
I am indebted to Prof. Dr. Dorothea Wagner (Konstanz) and Prof. Dr. Wilfried Hauenschild
(Paderborn) for co-reviewing this thesis.
Finally, I’d like to thank Ruth, my parents and my friends for their support and patience
during the last months when many evenings and weekends were taken up by this work.
Paderborn,
December 2002 Torsten Fahle
2partially funded by the ESPRIT programme of the Commission of the European Union as project number
24 960.
3partially supported by the Future and Emerging Technologies programme of the EU under contract number
IST-1999-14186 (ALCOM-FT).
4partly supported by the German Ministry for Education and Research Bmb+f (PARPAP project 01 HR 9955)
v



viContents
1 Introduction 1
1.1 Integrating Concepts from CP and OR . . . .................. 1
1.1.1 Basic of Integer Linear Programming and Constraint Pro-
gramming................................ 2
1.1.2 Strategic Considerations . . . . . ....... 4
1.1.3 Tactical......................... 4
1.2 Contribution of the Thesis . .......... 5
1.2.1 Airline Crew Rostering, Shortest Path Constraint and CP based Col-
umn Generation . . . . ......................... 5
1.2.2 Automatic Recording Problem, Knapsack Constraint and CP based
Lagrangian Relaxation ......................... 6
1.2.3 Home Health Care and Domain Filtering for Sequences .... 7
1.2.4 Maximum Clique and Comparing OR Bounds to CP Domain Filtering 8
2 Basic Concepts 9
2.1 Constraint Programming . . . ......................... 9
2.1.1 Consistency . . . . . .......... 1
2.1.2 Tree Search . . . . . . ......................... 14
2.2 Operations Research Approaches . . . . . ....... 15
2.2.1 LP-based Branch-and-Bound . . . . .................. 16
2.2.2 Column Generation . . ............. 17
2.2.3 Lagrangian Relaxation..................... 19
2.3 Integrated Approaches . . . . ............. 20
2.3.1 Cost Based Filtering ...................... 21
2.3.2 CP Based Column Generation . . ....... 2
2.3.3 CP Based Lagrangian Relaxation . .................. 23
2.4 Experimental Methodology . . ..................... 25
2.4.1 Software Packages . .............. 26
2.4.2 Benchmarks . . . . . . ..................... 26
2.4.3 Measuring Runtime . .............. 27
3 Cost Based Filtering for Knapsack Constraints 29
3.1 Constrained Knapsack Problems . . . . . . .................. 30
3.2 Applications for Constrained Knapsack Problems . . . .... 31
3.3 Constrained Knapsack vs. Pure . . . ........... 32
3.3.1 Variable Fixing for the Constrained Knapsack Problem .... 32viii Contents
3.3.2 Upper Bounds for Knapsack Problems................. 3
3.3.3 Reduction Techniques for Knapsack Problems . ....... 35
3.4 A Fast Filtering Algorithm based on BoundU andU ............ 361 2
3.5 More Effective Cost Based Filtering using BoundU ......... 383
3.6 Cost Based Filtering for Special Constrained Knapsack Problems . . . . . . . 38
3.6.1 Multi-Dimensional Knapsack Problems . . . . . . .......... 39
3.6.2 Bounded Knapsack Problems . . . . ............. 39
3.7 Numerical Evaluation . . ............................ 40
3.7.1 Test Environment............ 40
3.7.2 The Opponents . ............................ 41
3.7.3 Experimental Results . ............. 41
3.8 Conclusions ................................... 45
4 Airline Crew Rostering 47
4.1 Solving Airline Crew Rostering Problems . . ................. 47
4.1.1 The Airline Crew Assignment Problem . . . . . ....... 48
4.1.2 Current Solution Methods . . . . . . ................. 49
4.1.3 The Airline Test Case . . ................ 50
4.2 A Column Generation Model for the CAP . . ................. 51
4.2.1 The Subproblem .................... 51
4.2.2 Implementation ..................... 57
4.2.3 The Master Problem . . ................ 60
4.3 Overview of the Entire Approach.................... 61
4.4 Numerical Results . . . . .................... 62
4.5 Conclusions ........................... 65
5 Hybrid Approaches for Airline Crew Rostering 67
5.1 The Airline Test Cases . ............................ 67
5.2 Heuristic Tree Search Constraint Programming Approach ....... 68
5.2.1 Tree Traversal . ............................ 69
5.3 Constraint Programming based Column Generation Approach . . . . . . . . 69
5.3.1 Problems with Column Generation . . ................. 70
5.4 Integrating the Approaches . . . ................ 71
5.4.1 First Way of Integration: Transforming a Set Covering into a Set Par-
titioning Solution ............................ 71
5.4.2 Second Way of Integration: Generating Combinable Columns and Ex-
ploiting Dual Values . . ........................ 74
5.5 Numerical Results . . . . ................ 7
5.6 Combining Both Hybrid Methods . . . . . . ................. 79
5.7 Conclusions ........................... 80
6 Home Health Care 83
6.1 Introduction ................................... 83
6.1.1 Specific Requirements ............. 84
6.1.2 Literature Review............................ 85
6.2 A Mathematical Model for the Home Health Care Problem...... 85Contents ix
6.2.1 Parameters and Notation . . . . . . .................. 86
6.3 Solving Home Health Care Problems . . . ....... 90
6.3.1 Preprocessing . . . . . ......................... 91
6.3.2 Sequencing a Roster .......... 91
6.3.3 Initial Solutions via Constraint Programming . . ........... 93
6.3.4 Improvement Heuristics . . . . . . .......... 94
6.4 A Hybrid Solution Approach . ..................... 97
6.4.1 The Pool Concept . . . . . .......... 97
6.4.2 Using a Good Solution to Improve the Search . . ........... 98
6.4.3 Using the Essence of All Solutions . .......... 9
6.5 Numerical Evaluation . . . . . .....................10
6.5.1 Optimal Sequences . ..............101
6.5.2 Initial Solutions via Constraint Programming . . ...........102
6.5.3 Comparing the Heuristics . . . . . ..........103
6.5.4 Combining Approaches . . . . . ...............103
6.6 Conclusions . . . ........................105
7 The Automatic Recording Problem 107
7.1 An Integer Linear Programming Formulation . . . . . . ...........108
7.2 Solving the ARP via CP based Lagrangian Relaxation . ....109
7.2.1 Substructures of the ARP . . . . . . ..................10
7.2.2 CP based Lagrangian Relaxation for the ARP . ....10
7.2.3 Implementation Details.........................11
7.3 Numerical Results................112
7.3.1 Test Instance Generation . . . . . . ..................112
7.3.2 Numerical Results for Lagrangian Coupling . . ....13
7.4 Conclusions . . . ................................17
8 More Efficient Approaches for the Automatic Recording Problem 119
8.1 Solving the ARP via Branch-and-Cut . . . . ..................119
8.1.1 Valid Inequalities for the Vertex Cover Polytope ....120
8.1.2 Valid for the Knapsack Polytope . . ...........12
8.2 Solving the ARP via Dynamic Programming..........124
8.2.1 A Simple Approach . . .....................125
8.2.2 An Improved Dynamic Program . . ..........125
8.3 Results . . ................................127
8.3.1 Numerical Results for Branch-and-Cut and Dynamic Programming . 127
8.3.2 Comparing the Approaches . . . . . ..................131
8.4 Conclusion . . . ....................131
8.4.1 The Branch-and-Cut Approach . . . ..................132
8.4.2 The Dynamic Programming Approach . . . . . ....132
8.5 Extending the Basic Model . . .........................132
8.5.1 Avoiding Multiple Copies . . . . .......13
8.5.2 Using Multiple Recording Units . . ..................13
8.5.3 Using Storage Units . . .......134

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin