A polyhedral model for enumeration and optimization over the set of circuits
From MaRDI portal
Publication:2064285
Abstract: Circuits play a fundamental role in polyhedral theory and linear programming. For instance, circuits are used as step directions in various augmentation schemes for solving linear programs or to leave degenerate vertices while running the simplex method. However, there are significant challenges when implementing these approaches: The set of circuits of a polyhedron may be of exponential size and is highly sensitive to the representation of the polyhedron. In this paper, we provide a universal framework for enumerating the set of circuits and optimizing over sets of circuits of a polyhedron in any representation - we propose a polyhedral model in which the circuits of the original polyhedron are encoded as extreme rays or vertices. Many methods in the literature and software assume that a polyhedron is in standard form; our framework is a direct generalization. We demonstrate its value by showing that the conversion of a general representation to standard form may introduce exponentially many new circuits. We then discuss the main advantages of the generalized polyhedral model. It enables the direct enumeration of useful subsets of circuits such as strictly feasible circuits or sign-compatible circuits, as well as optimization over these sets. In particular, this leads to the efficient computation of a steepest-descent circuit, which can be used in an augmentation scheme for solving linear programs or the construction of sign-compatible circuit walks with additional
Recommendations
Cites work
- \(n\)-fold integer programming in cubic time
- A counterexample to the Hirsch conjecture
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- A polynomial oracle-time algorithm for convex integer minimization
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Algebraic and geometric ideas in the theory of discrete optimization
- An application of simultaneous diophantine approximation in combinatorial optimization
- Decomposition theorems for linear programs
- Edges versus circuits: a hierarchy of diameters in polyhedra
- Generating all vertices of a polyhedron is hard
- scientific article; zbMATH DE number 1254272 (Why is no real title available?)
- scientific article; zbMATH DE number 1860733 (Why is no real title available?)
- scientific article; zbMATH DE number 3365043 (Why is no real title available?)
- Nonlinear discrete optimization. An algorithmic theory
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- On Finding Primal- and Dual-Optimal Bases
- On the circuit diameter conjecture
- On the circuit diameter of dual transportation polyhedra
- On the circuit diameter of some combinatorial polytopes
- On the diameter of partition polytopes and vertex-disjoint cycle cover
- On the foundations of linear and integer linear programming I
- On the positive sums property and the computation of Graver test sets
- Variation of cost functions in integer programming
- Vector Space Decomposition for Solving Large-Scale Linear Programs
Cited in
(10)- Sublinear circuits for polyhedral sets
- Circuit walks in integral polyhedra
- scientific article; zbMATH DE number 7204563 (Why is no real title available?)
- Pivot rules for circuit-augmentation algorithms in linear optimization
- Inapproximability of shortest paths on perfect matching polytopes
- Circuits in extended formulations
- Circuit and Graver walks and linear and integer programming
- On the hardness of short and sign-compatible circuit walks
- Inapproximability of shortest paths on perfect matching polytopes
- On the circuit diameter conjecture for counterexamples to the Hirsch conjecture
This page was built for publication: A polyhedral model for enumeration and optimization over the set of circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2064285)
