Degeneracy Hunter: An Algorithm for Determining Irreducible Sets of Degenerate Constraints in Mathematical Programs

Degenerate constraints, i.e. constraints that violate the Linearly Independent Constraint Qualification (LICQ), are prevalent in many process optimization problems. These result from poor model formulations (typically human error) and overspecifications, zero flowrates and disappearing units, and loops. Because degenerate constraints lead to singular KKT systems and significant challenges to NLP solvers, these constraints complicate the solution procedure for nonlinear programs (NLPs). Although most modern NLP solvers implement counter-measures to detect and eliminate degeneracies, increased computational effort and convergence failures may still result. Instead, the best approach is to reformulate the original NLP model. Unfortunately, this is difficult for complex models with thousands of equations. This work describes the Degeneracy Hunter, an algorithm that systematically analyzes any iteration from a continuous mathematical program solver and determines irreducible sets of degenerate constraints. This tool allows the expert modeler to focus on only a handful of equations, instead of the thousands that make up a typical process optimization problem. The algorithm has been prototyped in MATLAB and analyzes derivative information exported from GAMS. Calculation of irreducible sets of degenerate equations is formulated as a mixed integer linear program. The algorithm has been applied to a non-convex, highly nonlinear Air Separation Unit (ASU) design problem with 15,000+ variables and constraints, which identified three sources of degenerate equations. Straightforward revisions of the model to remove these degenerate constraints resulted in a 16% decrease in average CPU time and less frequent termination at infeasible points. Identifying these degeneracies would have been virtually impossible without a systematic approach.