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 P the circuit-diameter is bounded by a polynomial in the input bit-size of P. This is in contrast with the best bounds for the combinatorial diameter of polyhedra. Interestingly, we show that the circuitaugmentation 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 0/1 polytopes, a monotone path of strongly polynomial length can be constructed using steepest improving edges.
Pivot rules for circuit-augmentation algorithms in linear optimization
Sanita', Laura
2022
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 P the circuit-diameter is bounded by a polynomial in the input bit-size of P. This is in contrast with the best bounds for the combinatorial diameter of polyhedra. Interestingly, we show that the circuitaugmentation 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 0/1 polytopes, a monotone path of strongly polynomial length can be constructed using steepest improving edges.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
