Skip to main content
Upcoming Events:

PhD Comprehensive Exam Part II: Carlos Suarez

Date & Time:
   Add All to Calendar

ITB 201

Event Contact:

Antoine Deza

Examination Committee
Franya Franek  (Chair)
Kai Huang  (Examiner)

Worst-case instances for pivot-based optimization algorithms


Rational decision-making through quantitative modelling and analysis is the guiding principle behind operations research, a field with several far-reaching applications across engineering, sciences, and industry. Finding optimal allocations of resources, scheduling tasks, and designing prototypes are a few of the areas operations research is concerned with. In many cases, these problems can be formulated or approximated as linear optimization problems, which involve maximizing or minimizing a linear function over a domain defined by a set of linear inequalities. The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization. While the simplex methods, i.e. pivot-based methods, follow an edge path, the interior point methods follow the central path. The algorithmic issues are closely related to the combinatorial and geometric structure of the feasible region. In the last few years, there has been substantial progress dealing with the largest diameter and curvature of polytopes including Santos’ counterexample of the Hirsch conjecture for the diameter of a polytope, and the counterexample by Allamigeon et al concerning the strong polynomiality of central-path following interior point methods.

Another recent development deals with lattice polytopes; that is, convex hulls of points with integer-valued coordinates. In particular, the upper bound of Kleinschmidt and Onn was strengthened by Del Pia and Michini, and then by Deza and Pournin. The proposal aims to show that the order of the bound for lattice polytopes is tight and to develop theoretical and computational framework to investigate challenging instances. Preliminary results indicate that structured lattice polytopes associated to projections of hypercubes form a promising pool of candidates to strengthen the current best bounds for lattice polytopes. While convex hull determination is a theoretically intractable question, instances of reasonable dimensions and grid-sizes can be computed by exploiting their combinatorial and geometric properties. The approach combines linear optimization theory and algorithms, combinatorial properties of lattice polytopes, and computational approaches to characterize worst-case behaviours and investigate the conjectured bounds.