Short simplex paths in lattice polytopes

DOI10.1007/S00454-020-00268-YzbMATH Open1487.90476arXiv1912.05712OpenAlexW3139496137MaRDI QIDQ2117352FDOQ2117352

Carla Michini, Alberto Del Pia

Publication date: 21 March 2022

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: The goal of this paper is to design a simplex algorithm for linear programs on lattice polytopes that traces `short' simplex paths from any given vertex to an optimal one. We consider a lattice polytope $P$ contained in $[0,k{]}^n$ and defined via $m$ linear inequalities. Our first contribution is a simplex algorithm that reaches an optimal vertex by tracing a path along the edges of $P$ of length in $O(n^{4}klog(nk)$. The length of this path is independent from $m$ and it is the best possible up to a polynomial function. In fact, it is only polynomially far from the worst-case diameter, which roughly grows as a linear function in $n$ and $k$. Motivated by the fact that most known lattice polytopes are defined via $0,pm1$ constraint matrices, our second contribution is an iterative algorithm which exploits the largest absolute value $alpha$ of the entries in the constraint matrix. We show that the length of the simplex path generated by the iterative algorithm is in $O(n^{2}klog(nkalpha))$. In particular, if $alpha$ is bounded by a polynomial in $n,k$, then the length of the simplex path is in $O(n^{2}klog(nk))$. For both algorithms, the number of arithmetic operations needed to compute the next vertex in the path is polynomial in $n$, $m$ and $logk$. If $k$ is polynomially bounded by $n$ and $m$, the algorithm runs in strongly polynomial time.

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

Recommendations

• Finding short paths on polytopes by the shadow vertex algorithm
• On the length of monotone paths in polyhedra
• scientific article; zbMATH DE number 2196286
• On the shadow simplex method for curved polyhedra
• Linear programming, the simplex algorithm and simple polytopes

zbMATH Keywords

lattice polytopesdiametersimplex algorithmstrongly polynomial time

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Scaling algorithms for network problems
• Factoring polynomials with rational coefficients
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the diameter of convex polytopes
• The Hirsch conjecture is true for (0,1)-polytopes
• On the diameter of lattice polytopes
• On the Length of Monotone Paths in Polyhedra
• Title not available (Why is that?)
• An application of simultaneous diophantine approximation in combinatorial optimization
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Title not available (Why is that?)
• A bound for the number of different basic solutions generated by the simplex method
• On the number of solutions generated by the dual simplex method
• Integer Programming
• On the maximal number of edges of convex digital polygons included into an \(m \times m\)-grid
• 0/1-Integer programming: Optimization and Augmentation are equivalent
• Improved bounds on the diameter of lattice polytopes
• Primitive zonotopes
• Solving MIPs via scaling-based augmentation
• Restarting algorithms: sometimes there is free lunch
• The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
• The diameter of lattice zonotopes

Cited In (3)

• Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization
• Lemke Paths on Simple Polytopes
• The complexity of geometric scaling

This page was built for publication: Short simplex paths in lattice polytopes

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