Solving totally unimodular LPs with the shadow vertex algorithm

DOI10.4230/LIPICS.STACS.2015.171MaRDI QIDQ2954993zbMATH OpenOpenAlexFDO

Authors Tobias Brunsch, Anna Großwendt, Heiko Röglin

Publication date 24 January 2017

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

zbMATH Keywords

linear optimizationsimplex algorithmshadow vertex method

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Abstract: We show that the shadow vertex simplex algorithm can be used to solve linear programs in strongly polynomial time with respect to the number $n$ of variables, the number $m$ of constraints, and $1/delta$, where $delta$ is a parameter that measures the flatness of the vertices of the polyhedron. This extends our recent result that the shadow vertex algorithm finds paths of polynomial length (w.r.t. $n$, $m$, and $1/delta$) between two given vertices of a polyhedron. Our result also complements a recent result due to Eisenbrand and Vempala who have shown that a certain version of the random edge pivot rule solves linear programs with a running time that is strongly polynomial in the number of variables $n$ and $1/delta$, but independent of the number $m$ of constraints. Even though the running time of our algorithm depends on $m$, it is significantly faster for the important special case of totally unimodular linear programs, for which $1/deltalen$ and which have only $O(n^2)$ constraints.

Recommendations

• Finding short paths on polytopes by the shadow vertex algorithm
• On the shadow simplex method for curved polyhedra
• On the shadow simplex method for curved polyhedra
• Geometric random edge
• A randomized polynomial-time simplex algorithm for linear programming

Cited in

(9)

• On the shadow simplex method for curved polyhedra
• A friendly smoothed analysis of the simplex method
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• On the shadow simplex method for curved polyhedra
• Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
• Determination of optimal vertices from feasible solutions in unimodular linear programming
• Finding short paths on polytopes by the shadow vertex algorithm
• Geometric random edge
• The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes

This page was built for publication: Solving totally unimodular LPs with the shadow vertex algorithm

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