McMaster University
Discrete Geometry and Optimization Approaches for Lattice Polytopes
Abstract
dc:description.abstractLinear 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).
Degree
thesis:*- Department dc:contributor.department
- Computing and Software
- Year dc:date.issued
- 2021
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Suarez, Carlos
- Advisor dc:contributor.advisor
-
- Deza, Antoine
Subjects
dc:subject × 4Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/14385