Proximity and Flatness Bounds for Linear Integer Optimization

Marcel Celaya (), Stefan Kuhlmann (), Joseph Paat () and Robert Weismantel ()
Additional contact information
Marcel Celaya: School of Mathematics, Cardiff University, Wales CF24 4AG, United Kingdom
Stefan Kuhlmann: Institut für Mathematik, Technische Universität Berlin, 10587 Berlin, Germany
Joseph Paat: Sauder School of Business, University of British Columbia, Vancouver, British Columbia V6T 1ZC, Canada
Robert Weismantel: Department of Mathematics, Institute for Operations Research, Eidgenössische Technische Hochschule Zürich, 8092 Zurich, Switzerland

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2446-2467

Abstract: This paper deals with linear integer optimization. We develop a technique that can be applied to provide improved upper bounds for two important questions in linear integer optimization. Given an optimal vertex solution for the linear relaxation, how far away is the nearest optimal integer solution (if one exists; proximity bounds)? If a polyhedron contains no integer point, what is the smallest number of integer parallel hyperplanes defined by an integral, nonzero, normal vector that intersect the polyhedron (flatness bounds)? This paper presents a link between these two questions by refining a proof technique that has been recently introduced by the authors. A key technical lemma underlying our technique concerns the areas of certain convex polygons in the plane; if a polygon K ⊆ R 2 satisfies τ K ⊆ K ° , where τ denotes 90 ° counterclockwise rotation and K ° denotes the polar of K , then the area of K ° is at least three.

Keywords: Primary: 90C10; 52B10; integer programming; bounded determinants; proximity; width (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0335 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:4:p:2446-2467

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().