Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, Γ‰cole polytechnique fΓ©dΓ©rale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Books and Book parts
  4. A parameterized linear formulation of the integer hull
 
book part or chapter

A parameterized linear formulation of the integer hull

Eisenbrand, Friedrich  
β€’
Rothvoss, Thomas
January 2026
Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Let 𝐴 βˆˆβ„€π‘šΓ—π‘› be an integer matrix with entries bounded by Ξ” in absolute value. Cook et al. (1986) have shown that there exists a universal matrix 𝐡 βˆˆβ„€π‘šβ€²Γ—π‘› with the following property: For each 𝑏 βˆˆβ„€π‘š, there exists a 𝑑 βˆˆβ„€π‘šβ€² such that the integer hull of the polyhedron 𝑃 ={π‘₯ βˆˆβ„π‘› :𝐴⁒π‘₯ ≀𝑏} is described by 𝑃𝐼 ={π‘₯ βˆˆβ„π‘› :𝐡⁒π‘₯ ≀𝑑}. Our main result is that 𝑑 is an affine function of 𝑏 as long as 𝑏 is from a fixed equivalence class of the lattice 𝐷 β‹…β„€π‘š. Here 𝐷 βˆˆβ„• is a number that depends on 𝑛 and Ξ” only. Furthermore, 𝐷 as well as the matrix 𝐡 can be computed in time depending on 𝑛 and Ξ” only. An application of this result is the solution of an open problem posed by Cslovjecsek et al. (SODA 2024) concerning the complexity of 2-stage-stochastic integer programming problems. The main tool of our proof is the classical theory of ChvΓ‘tal-Gomory cutting planes and the elementary closure of rational polyhedra.

  • Details
  • Metrics
Type
book part or chapter
DOI
10.1137/1.9781611978971.164
Author(s)
Eisenbrand, Friedrich  

EPFL

Rothvoss, Thomas
Date Issued

2026-01

Publisher

Society for Industrial and Applied Mathematics

Publisher place

Philadelphia, PA

Published in
Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
ISBN of the book

9781611978971

Start page

4560

End page

4571

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
FunderFunding(s)Grant NumberGrant URL

Swiss National Science Foundation

2318620

Available on Infoscience
January 8, 2026
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/257713
Logo EPFL, Γ‰cole polytechnique fΓ©dΓ©rale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. Β© EPFL, tous droits rΓ©servΓ©s