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

parametric integer programminginteger programming gapfixed dimension

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

(34)

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

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)