Skip to main content
Upcoming Events:

PhD Defence: Carlos Suarez

Date & Time:
   Add All to Calendar
Location:

https://mcmaster.zoom.us/j/95204253511?pwd=UGZRcGExSHFyUE9QemJWWEFmLzhrQT09

Meeting ID: 952 0425 3511
Passcode: 825253

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

Discrete geometry and optimization approaches for lattice polytopes

Overview

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