Generating general-purpose cutting planes for mixed-integer programs [Elektronische Ressource] / Franz Wesselmann

Franz Wesselmann

Sujets

• Wissenschaft

Informations

• Publié par: universitat_paderborn
• Publié le: 01 janvier 2010
• Nombre de lectures: 20
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Dissertation
Generating General-Purpose Cutting
Planes for Mixed-Integer Programs
Dipl.-Wirt.-Inform. Franz Wesselmann
Schriftliche Arbeit zur Erlangung des akademischen Grades
doctor rerum politicarum (dr. rer. pol.)
im Fach Wirtschaftsinformatik
eingereicht an der
Fakultät für Wirtschaftswissenschaften der
Universität Paderborn
Gutachter:
1. Prof. Dr. Leena Suhl
2. Prof. Dr. Quentin Louveaux
Paderborn, im November 2010And how is education supposed to make
me feel smarter? Besides, every time
I learn something new, it pushes some
old stuff out of my brain. Remem-
ber when I took that home winemaking
course, and I forgot how to drive?
Homer SimpsonAcknowledgements
This thesis is the result of the research work I carried out as a member of the
Decision Support & Operations Research (DS&OR) Lab at the University of
Paderborn. Completing this dissertation would not have been possible without
the support of many people.
Firstandforemost, Iwouldliketoexpressmydeepestgratitudetomysupervisor
Prof. Dr. Leena Suhl for giving me the opportunity to join her research group
and to write this thesis. Her constant support and valuable guidance over the
years contributed crucially to the completion of this work. I would like to thank
Prof. Dr. Uwe Suhl for his support, many fruitful discussions and for sharing his
long-time experience in developing software for solving linear and mixed-integer
programming problems with me. I am very grateful to Prof. Dr. Quentin
Louveaux for writing the second report on my thesis.
I furthermore wish to thank all my past and present colleagues at the DS&OR
Labfortheirclosecollaborationandforprovidinganexcellentworkingatmosphere.
I really enjoyed the stimulating discussions on scientific topics as well as the
interesting and amusing discussions on non-work related topics during coffee and
lunch breaks. In particular, I would like to thank my office colleagues Philipp
Christophel, Achim Koberstein, Thomas Siebers and Daniel Rudolph for their
support. I also wish to thank Viktor Dück, Stefan Kramkowski, Christian Temath
and Jörg Wiese for their advice and encouragement during the time of writing
this thesis.
Last but not least, I wish to thank my friends and family, especially my parents,
my brothers and my godfather for believing in me and supporting me. Special
thanks are due to Sonja for her encouragement, patience, understanding and for
reminding me from time to time that there is more to life than a thesis.
Paderborn, November 2010 Franz Wesselmann
vContents
1. Introduction 1
I. Foundations 5
2. Integer Programming Preliminaries 7
2.1. Mixed-Integer Programs . . . . . . . . . . . . . . . . . . . . . . . 7
2.2. Linear Programming Relaxation . . . . . . . . . . . . . . . . . . 9
2.3. Disjunctive Relaxation . . . . . . . . . . . . . . . . . . . . . . . . 13
3. Algorithms 21
3.1. Cutting Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2. Branch-and-Bound . . . . . . . . . . . . . . . . . . . . . . . . . . 24
II. State-of-the-Art 29
4. Single-Row Cutting Planes 31
4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2. Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3. Chvátal-Gomory Cuts . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4. Cutting Planes for MIPs . . . . . . . . . . . . . . . . . . . . . . . 43
5. Multi-Row Cutting Planes 77
5.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2. Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.3. Group Relaxations . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.4. Valid Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
viiContents
6. Required Work 95
III. Implementation and Numerical Results 99
7. Framework 101
7.1. MOPS - An MIP Solver . . . . . . . . . . . . . . . . . . . . . . . 101
7.2. Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8. Single-Row Cutting Plane Separators 115
8.1. Gomory Mixed-Integer Cuts . . . . . . . . . . . . . . . . . . . . . 115
8.2. K-Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.3. Combined Gomory Mixed-Integer Cuts . . . . . . . . . . . . . . . 121
8.4. Reduce-and-Split Cuts . . . . . . . . . . . . . . . . . . . . . . . . 124
8.5. Lift-and-Project Cuts . . . . . . . . . . . . . . . . . . . . . . . . 127
8.6. AnewPivotingProcedureforStrengtheningGomoryMixed-Integer
Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.7. Strong Chvátal-Gomory Cuts . . . . . . . . . . . . . . . . . . . . 141
18.8. {0, }-Chvátal-Gomory Cuts . . . . . . . . . . . . . . . . . . . . 1442
8.9. Computational Results . . . . . . . . . . . . . . . . . . . . . . . . 148
9. Multi-Row Cutting Plane Separators 161
9.1. Maximal Lattice-Free Convex Sets . . . . . . . . . . . . . . . . . 161
9.2. Selecting a Multi-Row Relaxation . . . . . . . . . . . . . . . . . . 167
9.3. Generating Intersection Cuts . . . . . . . . . . . . . . . . . . . . 168
9.4. Computational Results . . . . . . . . . . . . . . . . . . . . . . . . 171
10.Cutting Plane Selection and Management 185
10.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
10.2.Cut Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
10.3.Cut Pool and Cut Selection Algorithm . . . . . . . . . . . . . . . 193
10.4.Computational Results . . . . . . . . . . . . . . . . . . . . . . . . 198
11.Summary and Concluding Remarks 203
viiiContents
A. Benchmarking Environment 211
A.1. Hard- and Software . . . . . . . . . . . . . . . . . . . . . . . . . . 211
A.2. Test Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
A.3. Evaluation Methods . . . . . . . . . . . . . . . . . . . . . . . . . 213
B. Tables 215
C. Notation 263
List of Abbreviations 267
List of Figures 269
List of Tables 271
List of Algorithms 277
Bibliography 279
ix