Polynomial Upper Bounds on the Number of Differing Columns of Δ-Modular Integer Programs

Jon Lee (), Joseph Paat (), Ingo Stallknecht () and Luze Xu ()
Additional contact information
Jon Lee: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Joseph Paat: Sauder School of Business, University of British Columbia, Vancouver, British Columbia V6T 1Z2, Canada
Ingo Stallknecht: Department of Mathematics, Eidgenossische Technische Hochschule Zurich, 8092 Zurich, Switzerland
Luze Xu: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109

Mathematics of Operations Research, 2023, vol. 48, issue 4, 2267-2286

Abstract: We study integer-valued matrices with bounded determinants. Such matrices appear in the theory of integer programs (IPs) with bounded determinants. For example, an IP can be solved in strongly polynomial time if the constraint matrix is bimodular: that is, the determinants are bounded in absolute value by two. Determinants are also used to bound the ℓ 1 distance between IP solutions and solutions of its linear relaxation. One of the first to quantify the complexity of IPs with bounded determinants was Heller, who identified the maximum number of differing columns in a totally unimodular matrix. Each extension of Heller’s bound to general determinants has been superpolynomial in the determinants or the number of equations. We provide the first column bound that is polynomial in both values. For integer programs with box constraints, our result gives the first ℓ 1 distance bound that is polynomial in the determinants and the number of equations. Our result can also be used to derive a bound on the height of Graver basis elements that is polynomial in the determinants and the number of equations. Furthermore, we show a tight bound on the number of differing columns in a bimodular matrix; this is the first tight bound since Heller. Our analysis reveals combinatorial properties of bimodular IPs that may be of independent interest.

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

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1339 (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:48:y:2023:i:4:p:2267-2286

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 ().