Mixed Integer Linear Sets
Final Report Abstract
In der Praxis auftretende Optimierungsprobleme lassen sich häaufig mithilfe gemischt-ganzzahliger linearer Modelle auf mathematische Ebene übersetzen. Während die Theorie der linearen wie auch der (rein) ganzzahligen Optimierung recht weit entwickelt ist, gilt gleiches nicht für die gemischt-ganzzahlige Optimierung. Hauptziel des Forschungsprojekts war es deshalb Strukturresultate für gemischt-ganzzahlige lineare Systeme abzuleiten. Insbesondere sollte ein vielversprechender geometrischer Ansatz hinsichtlich der Analyse von Schnittebenen verallgemeinert werden. Da dieser Ansatz auf gitterpunktfreien Polyedern beruht stand vor allem die Erforschung der Eigenschaften dieser Polyeder im Vordergrund. Gemäß Projektantrag konzentrierten wir unsere Forschungsaktivität auf folgende Punkte: 1. Mixed integer Farkas type lemmas. 2. Finite cutting plane methods based on maximal lattice-free polyhedra. 3. Approximation of disjunctions derived from approximations of high dimensional maximal lattice-free polyhedra. 4. Polyhedrality of closures of maximal lattice-free polyhedra. 5. Polyhedral relaxations from several tableau rows. Die erzielten Ergebnisse übertreffen bei weitem die formulierten Erwartungen. Der neuartige Ansatz aus konnte generalisiert und die gitterpunktfreien Polyeder hinsichtlich ihrer Eigenschaften charakterisiert werden. Aus den Forschungsresultaten lässt sich eine Theorie für gitterpunktfreie Schnittebenen ableiten die – zusammen mit Ergebnissen anderer Wissenschaftler – die grundlegenden Fragen des Ansatzes beantwortet. Eine algorithmische Umsetzung der Ergebnisse steht noch aus.
