This dissertation is devoted to solving general mixed integer optimization problems. Our main focus is understanding and developing strong cutting planes for mixed integer linear programs through Gomory and Johnson's k-dimensional infinite group relaxation. Each cut generated from this problem has an associated function, and among the strongest are extreme functions. For k=1 , we give an algorithm for testing the extremality of piecewise linear (possibly discontinuous) functions with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We extend this algorithm to a large class of functions for k = 2 and develop theory for a more general result for k ≥ 2. For the k-dimensional infinite group relaxation, we prove that any minimal valid function that is continuous piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuéjols and Molinaro for k=2.
We also contribute to the understanding of cutting plane closures for mixed integer programs. Cutting planes derived from maximal lattice-free convex sets have recently been studied intensely by the integer programming community. Although some fairly general results were obtained by Andersen, Louveaux and Weismantel, and later by Averkov, some basic questions remain unresolved. We show that when the number of integer variables is two the triangle closure is a polyhedron and its number of facets can be bounded by a polynomial in the size of the input data. The techniques of our proof are also used to refine Cornuéjols and Margot's necessary conditions identifying valid inequalities as facet-defining and to obtain polynomial complexity results concerning the mixed integer hull.
Finally, we study the integer minimization of a quasiconvex polynomial with quasiconvex polynomial constraints. We propose a new algorithm that is an improvement upon the best known algorithm, which is attributed to Heinz. This improvement is achieved by applying a new modern Lenstra-type algorithm, finding optimal ellipsoid roundings, and considering sparse encodings of polynomials. Our algorithm achieves a time-complexity of 22nlog2(n) + O(n) in terms of the dimension n.
|Commitee:||De Loera, Jesus, Woodruff, David|
|School:||University of California, Davis|
|School Location:||United States -- California|
|Source:||DAI-B 75/01(E), Dissertation Abstracts International|
|Subjects:||Applied Mathematics, Mathematics, Operations research|
|Keywords:||Cutting planes, Infinite group problem, Lenstra's algorithm, Mixed integer programming, Triangle closure|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be