- Conference Paper
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. Show more
Book titleInteger Programming and Combinatorial Optimization. 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings
Journal / seriesLecture Notes in Computer Science
Pages / Article No.
Organisational unit03873 - Weismantel, Robert / Weismantel, Robert
NotesConference lecture held on June 9, 2020. Due to the Coronavirus (COVID-19) the conference was conducted virtually.
MoreShow all metadata