On $$\Delta $$ Δ -modular integer linear problems in the canonical form and equivalent problems

Dmitry Gribanov (), Ivan Shumilov (), Dmitry Malyshev () and Panos Pardalos ()
Additional contact information
Dmitry Gribanov: HSE University
Ivan Shumilov: Lobachevsky State University of Nizhny Novgorod
Dmitry Malyshev: HSE University
Panos Pardalos: University of Florida

Journal of Global Optimization, 2024, vol. 88, issue 3, No 3, 651 pages

Abstract: Abstract Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type $$\max \{c^\top x :A x = b,\, x \in {{\,\mathrm{\mathbb {Z}}\,}}^n_{\ge 0}\}$$ max { c ⊤ x : A x = b , x ∈ Z ≥ 0 n } , where all the entries of A, b, c are integer, parameterized by the number of rows of A and $$\Vert A\Vert _{\max }$$ ‖ A ‖ max . This class of problems is known under the name of ILP problems in the standard form, adding the word ”bounded” if $$x \le u$$ x ≤ u , for some integer vector u. Recently, many new sparsity, proximity, and complexity results were obtained for bounded and unbounded ILP problems in the standard form. In this paper, we consider ILP problems in the canonical form $$\begin{aligned} \max \{c^\top x :b_l \le A x \le b_r,\, x \in {{\,\mathrm{\mathbb {Z}}\,}}^n\}, \end{aligned}$$ max { c ⊤ x : b l ≤ A x ≤ b r , x ∈ Z n } , where $$b_l$$ b l and $$b_r$$ b r are integer vectors. We assume that the integer matrix A has the rank n, $$(n + m)$$ ( n + m ) rows, n columns, and parameterize the problem by m and $$\Delta (A)$$ Δ ( A ) , where $$\Delta (A)$$ Δ ( A ) is the maximum of $$n \times n$$ n × n sub-determinants of A, taken in the absolute value. We show that any ILP problem in the standard form can be polynomially reduced to some ILP problem in the canonical form, preserving m and $$\Delta (A)$$ Δ ( A ) , but the reverse reduction is not always possible. More precisely, we define the class of generalized ILP problems in the standard form, which includes an additional group constraint, and prove the equivalence to ILP problems in the canonical form. We generalize known sparsity, proximity, and complexity bounds for ILP problems in the canonical form. Additionally, sometimes, we strengthen previously known results for ILP problems in the canonical form, and, sometimes, we give shorter proofs. Finally, we consider the special cases of $$m \in \{0,1\}$$ m ∈ { 0 , 1 } . By this way, we give specialised sparsity, proximity, and complexity bounds for the problems on simplices, Knapsack problems and Subset-Sum problems.

Keywords: Integer linear programming; Knapsack problem; Subset-sum problem; Group minimization problem; Sparsity & proximity bounds; Empty simplex (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01165-9 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:jglopt:v:88:y:2024:i:3:d:10.1007_s10898-022-01165-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01165-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().