Constructing Lattice-Free Gradient Polyhedra in Dimension Two

Abstract

Lattice-free gradient polyhedra are optimality certificates for mixed integer convex minimization models. We consider how to construct these polyhedra for unconstrained models with two integer variables. A classic result of Bell, Doignon, and Scarf states that a lattice-free gradient polyhedron exists with at most four facets. We show how to construct a sequence of (not necessarily lattice-free) gradient polyhedra, each of which has at most four facets, that finitely converges to a lattice-free gradient polyhedron. Each update requires constantly many gradient evaluations (By gradient evaluation, we refer to inner product evaluation using gradients. For our updates we require at most 18 gradient evaluations.). This update procedure imitates the gradient descent algorithm, and consequently, it yields a gradient descent type of algorithm for problems with two integer variables. An open question is to improve the convergence rates to obtain a minimizer or a lattice-free set.