Parameterised Integer Programming, Integer Cones, and Related Problems
Gennady Shmonin · Habilitation Regulations of the Faculty of Mechanical Engineering (University of Paderborn) · 2007
Given an m ×n-matrix A and a polyhedron Q in R m , we want to find a vector b ∈ Q such that the system of linear inequalities Ax b has no integral solution.We refer to this problem as a parameterised integer (linear) programming problem.This is a generalisation of ordinary integer linear programming, as Q can be chosen to contain only a single vector in R m .Motivated by the celebrated algorithm of Lenstra (1983) for integer programming in fixed dimension, we restrict ourselves to the case when n is fixed and develop a polynomial-time algorithm for parameterised integer programming in fixed dimension.As an application of this result, we provide an algorithm that computes the integer programming gap of a family of integer programs, i.e., the maximum value of the difference max c x : Ax bmax c x : Ax b, x ∈ Z n over all b for which the integer program is feasible.Then, we consider integer programs in standard form,Matrix A und ein Polyeder Q im R m gegeben, dann suchen wir einen Vektor b ∈ Q, so dass das Ungleichungssystem Ax b keine ganzzahlige Lösung besitzt.Wir bezeichnen dieses Problem als parametrisierte ganzzahlige Programmierung.Dies ist eine Verallgemeinerung der gewöhnlichen ganzzahligen Programmierung, denn Q kann als ein einzelner Vektor des R m gewählt werden.Motiviert durch den vielgepriesenen Algorithmus von Lenstra (1983) für ganzzahlige Programmierung in fester Dimension, beschränken wir uns auf konstantes n und entwickeln für diesen Fall einen Polynomialzeit-Algorithmus für parametrisierte ganzzahlige Programmierung in fester Dimension.Als eine Anwendung dieses Resultats liefern wir einen Algorithmus, welcher den Integrality Gap einer Familie von ganzzahligen Programmen berechnet; das bedeutet die maximale Differenz max c x : Ax bmax c x : Ax b, x ∈ Z n über alle Vektoren b, für die das ganzzahlige Programm zulässig ist.Dann betrachten wir ganzzahlige Programme in Standardform, min c x : Ax = b, x ∈ Z n + und beweisen mehrere Schranken an die Anzahl der von Null verschiedenen Komponenten in einer optimalen Lösung.Es wird sich herausstellen, dass es stets eine optimale Lösung gibt, deren Anzahl der von Null verschiedenen Einträge sich durch ein Polynom in der Anzahl der Ungleichungen und der maximalen Größe der Einträge in A beschränken lässt.Dieses Ergebnis folgt aus dem ganzzahligen Analogon des Satzes von Carathéodory, welches in dieser Dissertation bewiesen wird.Diese Schranke ist besonders nützlich, wenn das ganzzahlige Programm aus bestimmten kombinatorischen Optimierungsproblemen abgeleitet ist und exponentiell viele Variablen enthält, denn nichtsdestotrotz können wir in diesem Fall die Existenz einer optimalen Lösung polynomieller Größe zeigen.Eine solche Anwendung ist das Cutting Stock-Problem.Die Spalten der Matrix A in der IP-Formulierung des Problems sind exakt die nicht-negativen ganzzahligen Lösungen der Knapsack-Ungleichung ax 1, womit ihre Anzahl exponentiell in der Eingabe ist.Dennoch können wir beweisen, dass eine optimale Lösung polynomieller Größe existiert und damit das Cutting Stock-Problem in NP liegt, was bis dato nicht bekannt war.Wir setzen die Untersuchung dieses ganzzahligen Programms fort und leiten einige Resultate für die Güte der LP-Relaxation bzw.des Integrality Gaps ab.Schließlich geben wir eine IP-Formulierung polynomieller Größe für das Cutting Stock-Problem an.First of all, I thank my supervisor Professor Dr. Friedrich Eisenbrand for introducing me to the subject of integer programming and combinatorial optimisation, his support and encouragement, invaluable help, and for many other things.I cannot imagine a better adviser and, due to this reason, had to follow him all the way during his practical study of the "travelling researcher problem."Almost all results presented in this thesis were obtained in collaboration with him.I am grateful to András Sebő for inviting me to visit his research group in Grenoble and many valuable discussions during my stay there, which gave rise to some results presented in Chapter 6.Yet, I thank him for his willingness to take the second assessment for this thesis.And of course, I thank my parents, my grandmother, all of my friends in Germany and Russia and, specially, Svetlana.6.5 Polynomial-size integer programs . . . . . . . . . . . . . .