Linear optimization is concerned with maximizing, or minimizing, a linear objective
function over a feasible region defined as the intersection of a finite number
of hyperplanes. Pivot-based simplex methods and central-path following interior
point methods are the computationally most efficient algorithms to solve linear
optimization instances. Discrete optimization further assumes that some of the
variables are integer-valued. This dissertation focuses on the geometric properties
of the feasible region under some structural assumptions. In the first part, we consider
lattice (d,k)-polytopes; that is, the convex hull of a set of points drawn from
{0,1,...,k}^d, and study the largest possible diameter, delta(d,k), that a lattice (d,k)-
polytope can achieve. We present novel properties and an enumeration algorithm
to determine previously unknown values of delta(d,k). In particular, we determine
the values for delta(3,6) and delta(5,3), and enumerate all the lattice (3,3)-polytopes
achieving delta(3,3). In the second part, we consider the convex hull of all the 2^(2^d - 1)
subsums of the 2^d - 1 nonzero {0,1}-valued vectors of length d, and denote by
a(d) the number of its vertices. The value of a(d) has been determined until d =8
as well as asymptotically tight lower and upper bounds for loga(d). This convex
hull forms a so-called primitive zonotope that is dual to the resonance hyperplane
arrangement and belongs to a family that is conjectured to include lattice polytopes
achieving the largest possible diameter over all lattice (d,k)-polytopes. We
propose an algorithm exploiting the combinatorial and geometric properties of the
input and present preliminary computational results. / Thesis / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/27062 |
| Date | January 2021 |
| Creators | Guan, Zhongyan |
| Contributors | Deza, Antoine, Franek, Frantisek, Computing and Software |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0018 seconds