Skip to main content
Upcoming Events:

PhD Defence: Carlos Suarez

Date & Time:
   Add All to Calendar

Meeting ID: 952 0425 3511
Passcode: 825253

Event Contact:
Franya Franek 
Kai Huang
Ned Nedialkov (Chair)
Reza Samavi
Tamon Stephen (External)
Antoine Deza (Supervisor)

Discrete geometry and optimization approaches for lattice polytopes



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).