An algorithm for constructing the skeleton graph of degenerate systems of linear inequalities
Open Access
- 13 April 2017
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 12 (4) , e0175819
Abstract
Derive the quantitative predictions of constraint-based models require of conversion algorithms to enumerate and construct the skeleton graph conformed by the extreme points of the feasible region, where all constraints in the model are fulfilled. The conversion is problematic when the system of linear constraints is degenerate. This paper describes a conversion algorithm that combines the best of two methods: the incremental slicing of cones that defeats degeneracy and pivoting for a swift traversal of the set of extreme points. An extensive computational practice uncovers two complementary classes of conversion problems. The two classes are distinguished by a practical measure of complexity that involves the input and output sizes. Detailed characterizations of the complexity classes and the corresponding performances of the algorithm are presented. For the benefit of implementors, a simple example illustrates the stages of the exposition.Keywords
This publication has 24 references indexed in Scilit:
- Extremal correlations of the tripartite no-signaling polytopeJournal of Physics A: Mathematical and Theoretical, 2011
- Popescu-Rohrlich Correlations as a Unit of NonlocalityPhysical Review Letters, 2005
- Simulating Maximal Quantum Entanglement without CommunicationPhysical Review Letters, 2005
- Nonlocal correlations as an information-theoretic resourcePhysical Review A, 2005
- Metabolic network structure determines key aspects of functionality and regulationNature, 2002
- How good are convex hull algorithms?Computational Geometry, 1997
- Enumerating extreme points of a highly degenerate polytopeComputers & Operations Research, 1994
- A new pivoting rule for solving various degeneracy problemsOperations Research Letters, 1992
- The maximum numbers of faces of a convex polytopeMathematika, 1970
- The generalized simplex method for minimizing a linear form under linear inequality restraintsPacific Journal of Mathematics, 1955