Open AccessAn algorithm for constructing the skeleton graph of degenerate systems of linear inequalities
Author(s) -
José Manuel Méndez Martínez
Publication year - 2017
Publication title -
plos one
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.99
H-Index - 332
ISSN - 1932-6203
DOI - 10.1371/journal.pone.0175819
Subject(s) - algorithm , degeneracy (biology) , tree traversal , degenerate energy levels , computer science , slicing , constraint (computer aided design) , set (abstract data type) , graph , simple (philosophy) , theoretical computer science , mathematics , bioinformatics , philosophy , physics , geometry , epistemology , quantum mechanics , world wide web , biology , programming language
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.