Proximity and flatness bounds for linear integer optimization

Celaya, Marcel ORCID: https://orcid.org/0000-0003-3480-4835, Kuhlmann, Stefan, Paat, Joseph and Weismantel, Robert 2024. Proximity and flatness bounds for linear integer optimization. Mathematics of Operations Research 49 (4) , pp. 2446-2467. 10.1287/moor.2022.0335

PDF - Accepted Post-Print Version Download (675kB)

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⊆R2 satisfies τK⊆K° , where τ denotes 90° counterclockwise rotation and K° denotes the polar of K, then the area of K° is at least three.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Institute for Operations Research and Management Sciences
ISSN:	0364-765X
Date of First Compliant Deposit:	5 March 2024
Date of Acceptance:	30 October 2023
Last Modified:	18 Dec 2024 14:45
URI:	https://orca.cardiff.ac.uk/id/eprint/166862

Actions (repository staff only)

Edit Item