Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/27285
Title: | Discrete Geometry and Optimization Approaches for Lattice Polytopes |
Authors: | Suarez, Carlos |
Advisor: | Deza, Antoine |
Department: | Computing and Software |
Keywords: | polytopes;lattices;diameter;optimization |
Publication Date: | 2021 |
Abstract: | Linear optimization aims at maximizing, or minimizing, a linear objective function over a feasible region defined by a finite number of linear constrains. For several well-studied problems such as maxcut, all the vertices of the feasible region are integral, that is, with integer-valued coordinates. The diameter of the feasible region is the diameter of the edge-graph formed by the vertices and the edges of the feasible region. This diameter is a lower bound for the worst-case behaviour for the widely used pivot-based simplex methods to solve linear optimization instances. A lattice (d,k)-polytope is the convex hull of a set of points whose coordinates are integer ranging from 0 to k. This dissertation provides new insights into the determination of the largest possible diameter δ(d,k) over all possible lattice (d,k)-polytopes. An enhanced algorithm to determine δ(d,k) is introduced to compute previously intractable instances. The key improvements are achieved by introducing a novel branching that exploits convexity and combinatorial properties, and by using a linear optimization formulation to significantly reduce the search space. In particular we determine the value for δ(3,7). |
URI: | http://hdl.handle.net/11375/27285 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Suarez_Carlos_A_2021Dic_PhD.pdf | 2.4 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.