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). / Thesis / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/27285 |
| Date | January 2021 |
| Creators | Suarez, Carlos |
| Contributors | Deza, Antoine, Computing and Software |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.002 seconds