Parametric integer programming in fixed dimension

DOI10.1287/MOOR.1080.0320MaRDI QIDQ3168997zbMATH OpenOpenAlexFDO

Authors Friedrich Eisenbrand, Gennady Shmonin

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.4336

zbMATH Keywords

fixed dimensioninteger programming gapparametric integer programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We consider the following problem: Given a rational matrix $Ainset{Q}^{mimesn}$ and a rational polyhedron $Qsubseteqset{R}^{m+p}$, decide if for all vectors $binset{R}^m$, for which there exists an integral $zinset{Z}^p$ such that $(b,z)inQ$, the system of linear inequalities $Axleqb$ 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 $maxcx:Axleqb,xinset{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 Hoc{s}ten and Sturmfels (2003) who presented such an algorithm for integer programs in standard form.

Recommendations

• scientific article; zbMATH DE number 1263257
• Gomory integer programs
• scientific article; zbMATH DE number 5761488
• Computational Complexity of Some Problems in Parametric Discrete Programming. I
• Parametric integer programming

Cited in

(37)

• Normal toric ideals of low codimension
• Parametric nonlinear integer programming: The right-hand side case
• FPT-algorithms for some problems related to integer programming
• LLL-reduction for integer knapsacks
• On lattice point counting in -modular polyhedra
• Distances to lattice points in knapsack polyhedra
• On the number of integer points in translated and expanded polyhedra
• The structure of an integral monoid and integer programming feasibility
• Parameterized resiliency problems
• Alternatives for testing total dual integrality
• Computing the integer programming gap
• Integer programming in parameterized complexity: five miniatures
• Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
• On polynomial kernels for sparse integer linear programs
• Parametrizing an integer linear program by an integer
• Parametric integer programming
• An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions
• scientific article; zbMATH DE number 5761488 (Why is no real title available?)
• Testing additive integrality gaps
• Computational Complexity of Some Problems in Parametric Discrete Programming. I
• scientific article; zbMATH DE number 1263257 (Why is no real title available?)
• Enumerating projections of integer points in unbounded polyhedra
• A randomized sieving algorithm for approximate integer programming
• Integer programming in parameterized complexity: three miniatures
• The Integrality Number of an Integer Program
• Sparse integer programming is FPT
• Short Presburger Arithmetic Is Hard
• The gap function: evaluating integer programming models over multiple right-hand sides
• The distributions of functions related to parametric integer optimization
• Parameterized resiliency problems via integer linear programming
• scientific article; zbMATH DE number 5165610 (Why is no real title available?)
• Parametric-objective integer programming using knapsack facets and Gomory cutting planes
• Designing optimization problems with diverse solutions
• Parameterized algorithms for block-structured integer programs with large entries
• Optimizing for strategy diversity in the design of video games
• Parametric integer programming algorithm for bilevel mixed integer programs
• Quantifier elimination over the integers

This page was built for publication: Parametric integer programming in fixed dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3168997)