Abstract
Lattice-free gradient polyhedra can be used to certify optimality for mixed integer convex minimization models. We consider how to construct these polyhedra for unconstrained models with two integer variables under the assumption that all level sets are bounded. In this setting, a classic result of Bell, Doignon, and Scarf states the existence of a lattice-free gradient polyhedron with at most four facets. We present an algorithm for creating a sequence of 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. Our updates imitate the gradient descent algorithm, and consequently, it yields a gradient descent type of algorithm for problems with two integer variables.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
We use ‘gradient evaluation’ to refer a single inner product evaluation using gradients, and ‘constantly many’ can be chosen to be 20 as counted in Table 1.
Case 2 requires 6 oracle calls while the others require only 4. This is also somewhat of an overestimate as one gradient may be reused over the course of multiple iterations.
References
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Bell, D.: A theorem concerning the integer lattice. Stud. Appl. Math. 56, 187–188 (1977)
Doignon, J.: Convexity in cristallographical lattices. J. Geom. 3, 71–85 (1973)
Scarf, H.: An observation on the structure of production sets with indivisibilities. Proc. Natl. Acad. Sci. U.S.A. 74, 3637–3641 (1977)
Baes, M., Oertel, T., Weismantel, R.: Duality for mixed-integer convex minimization. Math. Program. Ser. A 158, 547–564 (2016)
Basu, A., Conforti, M., Cornuéjols, G., Weismantel, R., Weltge, S.: Optimality certificates for convex minimization and Helly numbers. Op. Res. Let. 45, 671–674 (2017)
Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.A.: Inequalities from two rows of a simplex tableau. In Fischetti M., Williamson D.P., eds.: Integer Programming and Combinatorial Optimization (IPCO). Volume 4513 of Lecture Notes in Computer Science., Springer, Berlin, Heidelberg (2007)
Balas, E.: Intersection cuts - a new type of cutting planes for integer programming. Op. Res. 19(1), 19–39 (1971)
Basu, A., Conforti, M., Di Summa, M.: A geometric approach to cut-generating functions. Math. Program. 151(1), 153–189 (2015)
Basu, A., Cornuéjols, G., Köppe, M.: Unique minimal liftings for simplicial polytopes. Math. Op. Res. 37(2), 346–355 (2012)
Del Pia, A., Weismantel, R.: Relaxations of mixed integer sets from lattice-free polyhedra. 4OR 10(3), 221–244 (2012)
Averkov, G., Krümpelmann, J., Weltge, S.: Notions of maximality for integral lattice-free polyhedra: the case of dimension three. Mathematics of Operations Research 1035–1062 (2017)
Averkov, G., Wagner, C., Weismantel, R.: Maximal lattice-free polyhedra: Finiteness and an explicit description in dimension three. Math. Oper. Res. 721–742 (2011)
Basu, A., Conforti, M., Cornuéjols, G., Zambelli, G.: Maximal lattice-free convex sets in linear subspaces. Math. Op. Res. 35(3), 704–720 (2010)
Dey, S.S., Wolsey, L.A.: Lifting integer variables in minimal inequalities corresponding to lattice-free triangles. In Lodi A., Panconesi A., Rinaldi G., eds.: International Conference on Integer Programming and Combinatorial Optimization (IPCO). Volume 5035 of Lecture Notes in Computer Science., Springer, Berlin, Heidelberg (2008) 463 – 475
Lovász, L.: Geometry of numbers and integer programming. In M.Iri, Tanabe, K., eds.: Mathematical Programming: Recent Developments and Applications, Kluwer Academic Publishers (1989) 177 – 201
Gupta, O., Ravindran, V.: Branch and bound experiments in convex nonlinear integer programming. Manage. Sci. 31, 1533–1546 (1985)
Leyffer, S.: Integrating SQP and branch-and-bound for mixed integer nonlinear programming. Comput. Optim. Appl. 18, 295–309 (2001)
Bonami, P., Biegler, L.T., Conn, A.R., Cornuéjols, G., Grossman, I.E., Laird, C.D., Lee, J., Lodi, A., Margot, F., Sawaya, N., Wächter, A.: An algorithmic framework for convex mixed integer nonlinear programs. Discret. Opt. 5(2), 186–204 (2008)
Duran, M.A., Grossman, I.E.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Program. 36(3), 307–339 (1986)
Dadush, D., Peikert, C., Vempala, S.: Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. (2011) 580–589
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. 1 edn. Volume 2 of Algorithms and Combinatorics. Springer-Verlag Berlin Heidelberg (1988)
Baes, M., Oertel, T., Wagner, C., Weismantel, R.: Mirror-descent methods in mixed-integer convex optimization. In: Jünger, M., Reinelt, G. (eds.) Facets Comb. Op., pp. 101–131. Springer, Berlin, Heidelberg (2013)
Barvinok, A.: A Course in Convexity. Volume 54. Graduate Studies in Mathematics, American Mathematical Society, Providence, Rhode Island (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This paper extends work from an IPCO paper of the same title. This version includes complete proofs as well as new results on convergence for functions that are Lipschitz continuous and strongly convex.
Rights and permissions
About this article
Cite this article
Paat, J., Schlöter, M. & Speakman, E. Constructing lattice-free gradient polyhedra in dimension two. Math. Program. 192, 293–317 (2022). https://doi.org/10.1007/s10107-021-01658-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-021-01658-7