An algorithm for constructing the skeleton graph of degenerate systems of linear inequalities

Area of Science:

• Computational Biology
• Operations Research
• Mathematical Modeling

Background:

• Constraint-based models are crucial for quantitative predictions.
• Enumerating extreme points of the feasible region is essential for model conversion.
• Degenerate systems of linear constraints pose significant challenges for existing conversion algorithms.

Purpose of the Study:

• To develop a robust conversion algorithm for constraint-based models.
• To overcome the limitations of existing methods when dealing with degenerate constraints.
• To provide a detailed characterization of algorithm performance and complexity.

Main Methods:

• A novel conversion algorithm is introduced, combining incremental slicing of cones to handle degeneracy.
• Pivoting is employed for efficient traversal of the set of extreme points.
• Extensive computational experiments were conducted to analyze performance.

Main Results:

• The algorithm effectively defeats degeneracy in constraint-based models.
• Two complementary classes of conversion problems were identified based on complexity.
• The algorithm's performance is characterized in relation to input and output sizes.

Conclusions:

• The developed algorithm offers an effective solution for converting degenerate constraint-based models.
• The identified complexity classes provide insights into algorithm behavior.
• The findings benefit implementers by illustrating the algorithm's practical application.