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

Technische Universität MünchenZentrum Mathematikk-disjunctive cuts and cutting planealgorithms for general mixed integer linearprogramsMarkus JörgVollständiger Abdruck der von der Fakultät für Mathematik der Technischen UniversitätMünchen zur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften (Dr.rer.nat.)genehmigten Dissertation.Vorsitzender: Univ.-Prof.Dr.Martin BrokatePrüfer der Dissertation: 1. Univ.-Prof.Dr.Peter Gritzmann2.Dr.Robert WeismantelOtto-von-Guericke-Universität MagdeburgDie Dissertation wurde am 08.07.2008 bei der Technischen Universität Müncheneingereicht und durch die Fakultät für Mathematik am 20.11.2008 angenommen.AbstractIn this thesis we analyze cutting planes for general mixed integer linear programs from ageometric point of view and discuss some related algorithms. It is the main goal to findanswers to the following two fundamental questions: First, how can the mixed integerhull of an arbitrary polyhedron be generated by cutting planes? Secondly, how can aclassical cutting plane algorithm be designed which solves an arbitrary mixed integerlinear program exactly in finite time.The crucial result for dealing with these two problems is a natural generalization of thewell 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.