Jörg, Markus
[Verfasser:in]
;
Gritzmann, Peter
[Mitwirkende:r];
Gritzmann, Peter ;Weismantel, Robert
[Mitwirkende:r]
k-disjunctive cuts and cutting plane algorithms for general mixed integer linear programs ; k-disjunctive cuts und Schnittebenenalgorithmen für allgmeine gemischt-ganzzahlige lineare Programme
Titel:
k-disjunctive cuts and cutting plane algorithms for general mixed integer linear programs ; k-disjunctive cuts und Schnittebenenalgorithmen für allgmeine gemischt-ganzzahlige lineare Programme
Beteiligte:
Jörg, Markus
[Verfasser:in]
Erschienen:
Technical University of Munich; Technische Universität München, 2011-05-10
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
In this thesis we analyze cutting planes for general mixed integer linear programs from a geometric point of view and discuss some related algorithms. The main contribution is the introduction of cuts which are based on multi-term disjunctions and generalize the well known split cuts of Cook, Kannan, and Schrijver. These cuts allow us to answer 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. ; Die Dissertation beschäftigt sich mit Schnittebenen für allgemeine gemischt-ganzzahlige lineare Programme und zugehörigen Algorithmen. Im Mittelpunkt steht dabei eine Verallgemeinerung der bekannten Split Cuts von Cook, Kannan und Schrijver auf Schnittebenen, die auf Multiterm-Disjunktionen beruhen. Damit ist es möglich, die folgenden beiden grundsätzlichen Fragestellungen zu beantworten: Wie kann die gemischt-ganzzahlige Hülle eines beliebigen Polyeders mit Hilfe von Schnittebenen erzeugt werden? Wie kann ein klassischer Schnittebenenalgorithmus konstruiert werden, der ein beliebiges gemischt-ganzzahliges lineares Programm stets in endlicher Zeit exakt löst.