Méndez Martínez José Manuel, Urías Jesús
Instituto de Física, Universidad Autónoma de San Luis Potosí, San Luis Potosí, SLP, México.
PLoS One. 2017 Apr 13;12(4):e0175819. doi: 10.1371/journal.pone.0175819. eCollection 2017.
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.
推导基于约束的模型的定量预测需要转换算法来枚举和构建由可行区域的极点所符合的骨架图，在该可行区域中模型的所有约束都得到满足。当线性约束系统退化时，这种转换会出现问题。本文描述了一种结合两种方法优点的转换算法：克服退化的锥的增量切片和用于快速遍历极点集的 pivoting。广泛的计算实践揭示了两类互补的转换问题。这两类问题通过一种涉及输入和输出大小的实用复杂性度量来区分。给出了复杂性类别的详细特征以及算法的相应性能。为了便于实现者理解，一个简单的例子说明了阐述的各个阶段。
