IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v88y2024i3d10.1007_s10898-022-01165-9.html
   My bibliography  Save this article

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

Author

Listed:
  • Dmitry Gribanov

    (HSE University)

  • Ivan Shumilov

    (Lobachevsky State University of Nizhny Novgorod)

  • Dmitry Malyshev

    (HSE University)

  • Panos Pardalos

    (University of Florida)

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.

Suggested Citation

  • Dmitry Gribanov & Ivan Shumilov & Dmitry Malyshev & Panos Pardalos, 2024. "On $$\Delta $$ Δ -modular integer linear problems in the canonical form and equivalent problems," Journal of Global Optimization, Springer, vol. 88(3), pages 591-651, March.
  • Handle: RePEc:spr:jglopt:v:88:y:2024:i:3:d:10.1007_s10898-022-01165-9
    DOI: 10.1007/s10898-022-01165-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-022-01165-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10898-022-01165-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Éva Tardos, 1986. "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Research, INFORMS, vol. 34(2), pages 250-256, April.
    2. A. Yu. Chirkov & D. V. Gribanov & D. S. Malyshev & P. M. Pardalos & S. I. Veselov & N. Yu. Zolotykh, 2019. "On the complexity of quasiconvex integer minimization problem," Journal of Global Optimization, Springer, vol. 73(4), pages 761-788, April.
    3. Dmitriy S. Malyshev, 2014. "Boundary graph classes for some maximum induced subgraph problems," Journal of Combinatorial Optimization, Springer, vol. 27(2), pages 345-354, February.
    4. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    5. D. S. Malyshev, 2016. "A complexity dichotomy and a new boundary class for the dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 32(1), pages 226-243, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ilias Kotsireas & Panos Pardalos & Julius Žilinskas, 2024. "Preface," Journal of Global Optimization, Springer, vol. 88(3), pages 531-532, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. D. V. Gribanov & D. S. Malyshev & P. M. Pardalos & S. I. Veselov, 2018. "FPT-algorithms for some problems related to integer programming," Journal of Combinatorial Optimization, Springer, vol. 35(4), pages 1128-1146, May.
    2. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    3. K. Aardal & R. E. Bixby & C. A. J. Hurkens & A. K. Lenstra & J. W. Smeltink, 2000. "Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 192-202, August.
    4. Alberto Del Pia & Robert Hildebrand & Robert Weismantel & Kevin Zemmer, 2016. "Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 511-530, May.
    5. Ting Pong & Hao Sun & Ningchuan Wang & Henry Wolkowicz, 2016. "Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem," Computational Optimization and Applications, Springer, vol. 63(2), pages 333-364, March.
    6. R. B. Bapat & S. K. Neogy, 2016. "On a quadratic programming problem involving distances in trees," Annals of Operations Research, Springer, vol. 243(1), pages 365-373, August.
    7. Amitai Armon & Iftah Gamzu & Danny Segev, 2014. "Mobile facility location: combinatorial filtering via weighted occupancy," Journal of Combinatorial Optimization, Springer, vol. 28(2), pages 358-375, August.
    8. Balaji Gopalakrishnan & Seunghyun Kong & Earl Barnes & Ellis Johnson & Joel Sokol, 2011. "A least-squares minimum-cost network flow algorithm," Annals of Operations Research, Springer, vol. 186(1), pages 119-140, June.
    9. Klaus Jansen & Roberto Solis-Oba, 2011. "A Polynomial Time OPT + 1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 743-753, November.
    10. Clemens Heuberger, 2004. "Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 329-361, September.
    11. Friedrich Eisenbrand & Gennady Shmonin, 2008. "Parametric Integer Programming in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 839-850, November.
    12. Elizabeth Baldwin & Paul Klemperer, 2019. "Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities," Econometrica, Econometric Society, vol. 87(3), pages 867-932, May.
    13. Jaykrishnan, G. & Levin, Asaf, 2024. "Scheduling with cardinality dependent unavailability periods," European Journal of Operational Research, Elsevier, vol. 316(2), pages 443-458.
    14. Masing, Berenike & Lindner, Niels & Borndörfer, Ralf, 2022. "The price of symmetric line plans in the Parametric City," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 419-443.
    15. Amitabh Basu & Jesús A. De Loera & Mark Junod, 2014. "On Chubanov's Method for Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 336-350, May.
    16. Sanchari Deb & Kari Tammi & Karuna Kalita & Pinakeswar Mahanta, 2018. "Review of recent trends in charging infrastructure planning for electric vehicles," Wiley Interdisciplinary Reviews: Energy and Environment, Wiley Blackwell, vol. 7(6), November.
    17. Dmitry Gribanov & Ivan Shumilov & Dmitry Malyshev & Nikolai Zolotykh, 2024. "Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems," Journal of Global Optimization, Springer, vol. 89(4), pages 1033-1067, August.
    18. Kenneth J. Arrow & Timothy J. Kehoe, 1994. "Distinguished Fellow: Herbert Scarf's Contributions to Economics," Journal of Economic Perspectives, American Economic Association, vol. 8(4), pages 161-181, Fall.
    19. Kubale, Marek, 1996. "Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors," European Journal of Operational Research, Elsevier, vol. 94(2), pages 242-251, October.
    20. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:88:y:2024:i:3:d:10.1007_s10898-022-01165-9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.