On integer programming with bounded determinants

DOI10.1007/S11590-015-0943-YMaRDI QIDQ315478zbMATH OpenOpenAlexFDO

Authors S. I. Veselov, Dmitriy V. Gribanov

Publication date 21 September 2016

Published in Optimization Letters (Search for Journal in Brave)

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

zbMATH Keywords

simplexinteger programmingpolytopefeasibility problemempty latticeflatness theoremgroup minimization

Mathematics Subject Classification ID

Integer programming (90C10)

Abstract: Let $A$ be an $(mimesn)$ integral matrix, and let $P=x:Axleqb$ be an $n$-dimensional polytope. The width of $P$ is defined as $w(P)=minxinmathbb{Z}^{n}setminus0::ma{x}_{xinP}{x}^{o}pu-mi{n}_{xinP}{x}^{o}pv$. Let $Delta(A)$ and $delta(A)$ denote the greatest and the smallest absolute values of a determinant among all $r(A)imesr(A)$ sub-matrices of $A$, where $r(A)$ is the rank of a matrix $A$. We prove that if every $r(A)imesr(A)$ sub-matrix of $A$ has a determinant equal to $pmDelta(A)$ or $0$ and $w(P)ge(Delta(A)-1)(n+1)$, then $P$ contains $n$ affine independent integer points. Also we have similar results for the case of emph{$k$-modular} matrices. The matrix $A$ is called emph{totally $k$-modular} if every square sub-matrix of $A$ has a determinant in the set $0,,pm{k}^r::rinmathbbN$. When $P$ is a simplex and $w(P)gedelta(A)-1$, we describe a polynomial time algorithm for finding an integer point in $P$. Finally we show that if $A$ is emph{almost unimodular}, then integer program $max{c}^{o}px::xinPcapmathbb{Z}^n$ can be solved in polynomial time. The matrix $A$ is called emph{almost unimodular} if $Delta(A)leq2$ and any $(r(A)-1)imes(r(A)-1)$ sub-matrix has a determinant from the set $0,pm1$.

Recommendations

• The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
• A strongly polynomial algorithm for bimodular integer linear programming
• Integer program with bimodular matrix
• Enumerating integer points in polytopes with bounded subdeterminants
• The width and integer optimization on simplices with bounded minors of the constraint matrices

Cites work

• scientific article; zbMATH DE number 3828715 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 1342145 (Why is no real title available?)
• scientific article; zbMATH DE number 3046578 (Why is no real title available?)
• A bidirected generalization of network matrices
• A study of the boundary graph classes for colorability problems
• Boundary properties of graphs for algorithmic graph problems
• Classes of graphs critical for the edge list-ranking problem
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• Continuous sets of the boundary classes of graphs for coloring problems
• Covering minima and lattice-point-free convex bodies
• Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
• FACES OF AN INTEGER POLYHEDRON
• Faster deterministic volume estimation in the oracle model via thin lattice coverings
• Handbook of global optimization
• Independent sets in the graphs with bounded minors of the extended incidence matrix
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\). II: Application of \(K\)-convexity
• Integer program with bimodular matrix
• ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
• On minimal complex classes of graphs
• On the maximal width of empty lattice simplices
• Polynomial algorithms in linear programming
• Some polyhedra related to combinatorial problems
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
• The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
• The Maximum Independent Set Problem in Planar Graphs
• The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem

Cited in

(21)

• On the recognition of \(\{a,b,c\}\)-modular matrices
• Fully Bounded Polyhedral Analysis of Integers with Wrapping
• scientific article; zbMATH DE number 5165610 (Why is no real title available?)
• Generalized Chvátal-Gomory closures for integer programs with bounds on variables
• An integer programming problem and rank decomposition of block upper triangular matrices
• On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
• Integer program with bimodular matrix
• scientific article; zbMATH DE number 609981 (Why is no real title available?)
• Notes on \(\{a,b,c\}\)-modular matrices
• On lattice point counting in \(\varDelta\)-modular polyhedra
• Enumerating integer points in polytopes with bounded subdeterminants
• Complexity of optimizing over the integers
• The width and integer optimization on simplices with bounded minors of the constraint matrices
• Polynomial Upper Bounds on the Number of Differing Columns of Δ-Modular Integer Programs
• Advances on strictly \(\varDelta \)-modular IPs
• Enumeration and unimodular equivalence of empty delta-modular simplices
• A note on non-degenerate integer programs with small sub-determinants
• FPT-algorithms for some problems related to integer programming
• On lattice width of lattice-free polyhedra and height of Hilbert bases
• On the maximal number of columns of a \(\varDelta \)-modular matrix
• 2-modular matrices

This page was built for publication: On integer programming with bounded determinants

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