Pivot rules for circuit-augmentation algorithms in linear optimization
From MaRDI portal
Abstract: Circuit-augmentation algorithms are generalizations of the Simplex method, where in each step one is allowed to move along a fixed set of directions, called circuits, that is a superset of the edges of a polytope. We show that in the circuit-augmentation framework the greatest-improvement and Dantzig pivot rules are NP-hard, already for 0/1-LPs. Differently, the steepest-descent pivot rule can be carried out in polynomial time in the 0/1 setting, and the number of circuit augmentations required to reach an optimal solution according to this rule is strongly-polynomial for 0/1-LPs. The number of circuit augmentations has been of interest as a proxy for the number of steps in the Simplex method, and the circuit-diameter of polyhedra has been studied as a lower bound to the combinatorial diameter of polyhedra. Extending prior results, we show that for any polyhedron the circuit-diameter is bounded by a polynomial in the input bit-size of . This is in contrast with the best bounds for the combinatorial diameter of polyhedra. Interestingly, we show that the circuit-augmentation framework can be exploited to make novel conclusions about the classical Simplex method itself: In particular, as a byproduct of our circuit results, we prove that (i) computing the shortest (monotone) path to an optimal solution on the 1-skeleton of a polytope is NP-hard, and hard to approximate within a factor better than 2, and (ii) for polytopes, a monotone path of strongly-polynomial length can be constructed using steepest improving edges.
Recommendations
Cites work
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- scientific article; zbMATH DE number 1241836 (Why is no real title available?)
- scientific article; zbMATH DE number 1538119 (Why is no real title available?)
- scientific article; zbMATH DE number 835749 (Why is no real title available?)
- scientific article; zbMATH DE number 2196286 (Why is no real title available?)
- scientific article; zbMATH DE number 3365043 (Why is no real title available?)
- 0/1-Integer programming: Optimization and Augmentation are equivalent
- A bound for the number of different basic solutions generated by the simplex method
- A polyhedral model for enumeration and optimization over the set of circuits
- A polynomial oracle-time algorithm for convex integer minimization
- Algebraic and geometric ideas in the theory of discrete optimization
- An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
- An application of simultaneous diophantine approximation in combinatorial optimization
- An exponential lower bound for Cunningham's rule
- Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm
- Decomposition theorems for linear programs
- Edges versus circuits: a hierarchy of diameters in polyhedra
- Extremal properties of 0/1-polytopes
- Fractional perfect \(b\)-matching polytopes. I: General theory
- Gröbner bases and triangulations of the second hypersimplex
- Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
- Network flows. Theory, algorithms, and applications.
- Nonlinear discrete optimization. An algorithmic theory
- Note on Weintraub’s Minimum-Cost Circulation Algorithm
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- On Simplex Pivoting Rules and Complexity Theory
- On the circuit diameter of dual transportation polyhedra
- On the circuit diameter of some combinatorial polytopes
- On the complexity of computing the diameter of a polytope
- On the number of solutions generated by the simplex method for LP
- Pivot rules for linear programming: A survey on recent theoretical developments
- Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications
- Short simplex paths in lattice polytopes
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
- The Complexity of Generic Primal Algorithms for Solving General Integer Programs
- The complexity of the simplex method
- The simplex algorithm with the pivot rule of maximizing criterion improvement
- What is the worst case behavior of the simplex algorithm?
- Worst case behavior of the steepest edge simplex method
Cited in
(13)- Inapproximability of shortest paths on perfect matching polytopes
- Circuits in extended formulations
- On combinatorial network flows algorithms and circuit augmentation for pseudoflows
- On the hardness of short and sign-compatible circuit walks
- On the number of degenerate simplex pivots
- On circuit diameter bounds via circuit imbalances
- Shortest paths on polymatroids and hypergraphic polytopes
- Exponential lower bounds for many pivot rules for the simplex method
- A polyhedral model for enumeration and optimization over the set of circuits
- Inapproximability of shortest paths on perfect matching polytopes
- A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
- Circuit and Graver walks and linear and integer programming
- Circuit walks in integral polyhedra
This page was built for publication: Pivot rules for circuit-augmentation algorithms in linear optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5867626)
