On a Simple Connection Between $$\Delta$$ Δ -Modular ILP and LP, and a New Bound on the Number of Integer Vertices

Dmitry Gribanov (), Dmitry Malyshev () and Ivan Shumilov ()
Additional contact information
Dmitry Gribanov: National Research University Higher School of Economics
Dmitry Malyshev: National Research University Higher School of Economics
Ivan Shumilov: Lobachevsky State University of Nizhny Novgorod

SN Operations Research Forum, 2024, vol. 5, issue 2, 1-9

Abstract: Abstract In our note, we present a very simple and short proof of a new interesting fact about the faces of an integer hull of a given rational polyhedron. This fact has a complete analog in linear programming theory and can be useful to establish new constructive upper bounds on the number of vertices in an integer hull of a $$\Delta$$ Δ -modular polyhedron, which are competitive for small values of $$\Delta$$ Δ and can be useful for integer linear maximization problems with a convex or quasiconvex objective function. As an additional corollary, we show that the number of vertices in an integer hull is bounded by $$O(n)^n$$ O ( n ) n for $$\Delta = O(1)$$ Δ = O ( 1 ) . As a part of our method, we introduce the notion of deep bases of a linear program. The problem to estimate their number by a non-trivial way seems to be quite challenging.

Keywords: Linear programming; Integer linear programming; Number of vertices; $$\Delta$$ Δ -modular (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-024-00310-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:snopef:v:5:y:2024:i:2:d:10.1007_s43069-024-00310-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-024-00310-2

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().