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. Journal articles
  4. Parametric integer programming in fixed dimension
 
research article

Parametric integer programming in fixed dimension

Eisenbrand, Friedrich  
•
Shmonin, Gennady
2008
Mathematics of Operations Research

We consider the following problem: Given a rational matrix $A \in \mathbb{Q}^{m \times n}$ and a rational polyhedron $Q \subseteq \mathbb{R}^{m+p}$, decide if for all vectors $b \in \mathbb{R}^m$, for which there exists an integral $z \in \mathbb{Z}^p$ such that $(b, z) \in Q$, the system of linear inequalities $A x \leq b$ has an integral solution. We show that there exists an algorithm that solves this problem in polynomial time if $p$ and $n$ are fixed. This extends a result of Kannan (1990) who established such an algorithm for the case when, in addition to $p$ and $n$, the affine dimension of $Q$ is fixed. As an application of this result, we describe an algorithm to find the maximum difference between the optimum values of an integer program $\max { c^T x : A x \leq b, x \in \mathbb{Z}^n }$ and its linear programming relaxation over all right-hand sides $b$, for which the integer program is feasible. The algorithm is polynomial if $n$ is fixed. This is an extension of a recent result of Ho\c{s}sten and Sturmfels (2003) who presented such an algorithm for integer programs in standard form.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

preprint_parametric integer.pdf

Access type

openaccess

Size

165.48 KB

Format

Adobe PDF

Checksum (MD5)

85b84a4597529697d711c554e35291c4

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