Applications of the Dulmage-Mendelsohn decomposition for debugging nonlinear optimization problems

Nonlinear modeling and optimization is a valuable tool for aiding decisions by engineering practitioners, but programming an optimization problem based on a complex electrical, mechanical, or chemical process is a time-consuming and error-prone activity. Therefore, there is a need for model analysis and debugging tools that can detect and diagnose modeling errors. One such tool is the Dulmage-Mendelsohn decomposition, which identifies structurally under-and over-determined subsets in systems of equations and variables by partitioning the bipartite graph of the system. This work provides the necessary background to understand the Dulmage-Mendelsohn decomposition and its application to the analysis of nonlinear optimization problems, demonstrates its use in diagnosing a variety of modeling errors, and introduces software implementations for analyzing nonlinear optimization problems in the Pyomo and JuMP algebraic modeling languages.

Automated summary

Nonlinear modeling and optimization is valuable in decision-making for engineering practitioners, but programming these optimization problems based on complex processes can be time-consuming and prone to errors. The Dulmage-Mendelsohn decomposition is a tool that can detect and diagnose modeling errors by partitioning the bipartite graph of the system. This research provides background on the decomposition and its application to nonlinear optimization problems, demonstrates its use in diagnosing various modeling errors, and introduces software implementations for analyzing these problems in Pyomo and JuMP algebraic modeling languages.