k-disjunctive cuts and cutting plane algorithms for general mixed integer linear programs [Elektronische Ressource] / Markus Jörg

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2008
• Nombre de lectures: 19
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Technische Universität München
Zentrum Mathematik
k-disjunctive cuts and cutting plane
algorithms for general mixed integer linear
programs
Markus Jörg
Vollständiger Abdruck der von der Fakultät für Mathematik der Technischen Universität
München zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr.rer.nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof.Dr.Martin Brokate
Prüfer der Dissertation: 1. Univ.-Prof.Dr.Peter Gritzmann
2.Dr.Robert Weismantel
Otto-von-Guericke-Universität Magdeburg
Die Dissertation wurde am 08.07.2008 bei der Technischen Universität München
eingereicht und durch die Fakultät für Mathematik am 20.11.2008 angenommen.Abstract
In this thesis we analyze cutting planes for general mixed integer linear programs from a
geometric point of view and discuss some related algorithms. It is the main goal to find
answers to the following two fundamental questions: First, how can the mixed integer
hull of an arbitrary polyhedron be generated by cutting planes? Secondly, how can a
classical cutting plane algorithm be designed which solves an arbitrary mixed integer
linear program exactly in finite time.
The crucial result for dealing with these two problems is a natural generalization of the
well known split cuts of Cook, Kannan, and Schrijver to cuts which are based on multi-
term disjunctions. We call themk-disjunctive cuts and analyze their properties in detail.
These cuts allow us to answer the first question. We also provide a way for constructing
k-disjunctive cuts and show how they can be combined with classical cutting planes to
obtain a finite cutting plane algorithm for rational mixed integer linear programs.
We complete our explanations with a geometric comparison of some well known cutting
planes, an analysis of their properties in generating the mixed integer hull of a poly-
hedron, as well as a consideration of their algorithmic performance. Moreover, we give
some examples and applications to illustrate our theoretical results.
iiiZusammenfassung
Die vorliegende Arbeit beschäftigt sich mit Schnittebenen für allgemeine gemischt-ganz-
zahlige lineare Programme und zugehörigen Algorithmen. Dabei werden vor allem die
beiden folgenden Fragestellungen untersucht: Wie kann die gemischt-ganzzahlige Hülle
eines beliebigen Polyeders mit Hilfe von Schnittebenen bestimmt werden? Wie kann ein
klassischer Schnittebenenalgorithmus konstruiert werden, der ein beliebiges gemischt-
ganzzahliges lineares Programm stets in endlicher Zeit exakt löst? Grundlegend für die
Untersuchung der beiden Probleme ist dabei eine geometrische Vorgehensweise.
Der zentrale Ansatz zur Lösung der beiden Problemstellungen besteht in einer Verallge-
meinerungderbekanntenSplitCutsvonCook, KannanundSchrijveraufSchnittebenen,
die auf Multiterm Disjunktionen beruhen. Diese Klasse von Schnittebenen wird dabei
als k-disjunctive cuts bezeichnet und im Detail untersucht. Mit Hilfe dieser Schnitt-
ebenen ist es nun auf natürliche Weise möglich, eine Antwort auf die erste Frage zu
finden. Ebenso eröffnet ein konstruktives Verfahren zur Berechnung von k-disjunctive
cuts die Möglichkeit, einen endlichen Schnittebenenalgorithmus für rationale gemischt-
ganzzahlige Programme anzugeben.
Die Ausführungen in dieser Arbeit werden dabei ergänzt durch einen geometrischen
Vergleich einiger bekannter Schnittebenen sowie eine Untersuchung ihrer Eigenschaften
beim Bestimmen der gemischt-ganzzahligen Hülle eines Polyeders bzw. bei Verwendung
in einem Schnittebenenalgorithmus. Außerdem werden die theoretischen Ergebnisse
anhand einiger Beispiele und Anwendungen illustriert.
iiiivContents
Abstract i
Zusammenfassung iii
List of Symbols vii
List of Figures ix
1 Introduction 1
1.1 Overview and results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 General foundations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Cutting planes for MILP 13
2.1 Chvátal-Gomory cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Cuts for general MILP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Split cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Intersection cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.3 Mixed integer Gomory cuts . . . . . . . . . . . . . . . . . . . . . 24
2.2.4 integer rounding inequalities . . . . . . . . . . . . . . . . . 30
2.2.5 Strengthening of mixed integer cuts . . . . . . . . . . . . . . . . . 32
2.2.6 Cuts from two rows of the simplex tableau . . . . . . . . . . . . . 34
3 k-disjunctive cuts 37
3.1 Basic definitions and properties . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Approximation property of split cuts . . . . . . . . . . . . . . . . . . . . 44
3.3 Characterization of the mixed integer hull . . . . . . . . . . . . . . . . . 46
3.4 Computing k-disjunctive cuts . . . . . . . . . . . . . . . . . . . . . . . . 57
3.5 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4 Algorithms for MILP 65
4.1 Basic algorithm and problems . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2 Approximation algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1 Algorithm of Owen and Mehrotra . . . . . . . . . . . . . . . . . . 67
4.2.2 Searching for feasible points . . . . . . . . . . . . . . . . . . . . . 70
vContents
4.3 Exact algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3.1 Basic form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3.2 Computing extreme rays of cones . . . . . . . . . . . . . . . . . . 80
4.3.3 Irredundant representation of projections . . . . . . . . . . . . . . 84
4.3.4 Sequential algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.3.5 Examples and applications . . . . . . . . . . . . . . . . . . . . . . 89
5 Discussion 97
Bibliography 99
Index 103
viList of Symbols
Special sets
; the empty set
N,N the set of natural numbers excluding and including 0,0
respectively.
Z the set of the integers
Q the set of the rational numbers
R the set of the real numbers
B the set of all bases B
Operations on sets
AB A is subset of B or A =B
bd (S) the boundary of a set S
int (S) the interior of a set S
ext (S) the set of all extreme points of a set S
relbd (S) the relative boundary of a set S
relint (S) thee interior of a set S
conv (S) the convex hull of a set S
jSj the cardinality of a set S
p+q pproj (S) the projection of the set S R on the space R ofX
x-variables
dim(S) the dimension of the smallest affine subspace that con-
tains S
Polyhedra, closures, and disjunctions
P polyhedron of the feasible domain of the LP relaxation
of a (mixed) integer program
P the (mixed) integer hull of a polyhedron PI
iP the set of all feasible points of the LP relaxation in step
i of a cutting plane algorithm
viiList of Symbols
(i)P the i-th split closure of a (mixed integer) polyhedron P
or the i-th Chvátal-Gomory closure of a (integer) poly-
hedron P, respectively
(i)
P the i-th k-disjunctive closure of a polyhedron P
k
(i)
P the i-th irrational k-disjunctive closure of a polyhedronirr;k
P
D(d;) a split disjunction dx_dx + 1
D(k;d;) a k-disjunction dx
D (k;d;) an irrational k-disjunction dxirr
Miscellaneous
jxj the absolute value of x
jjxjj the norm of a vector x
bxc the largest integer less or equal to x
dxe the smallest integer greater or equal to x
+(x) the maximum of 0 and x
(x) theum of 0 and x
sign(x) the sign of x
xy the scalar product of two vectors of equal size
O Landau symbol
^;_ logical ’and’, ’or
viii