Debugging JuMP optimization models using graph theory

Writing a large optimization model is a time-consuming and error-prone task. If and when a modeling error is suspected, the developer often must re-consider every constraint in the model for faulty assumptions causing singularities in the optimization model, which impede convergence of solvers. We introduce a package that computes the Dulmage-Mendelsohn and block triangular partitions of incidence graphs of JuMP models, which can be used to detect sources of structural and numeric singularities.

The package we implement is named "JuMP-Incidence" or "JuMPIn.jl". It depends on JuMP and Graphs.jl, and may be of interest to the JuMP and Julia-Graphs communities. This package is of particular interest as model debugging is a notorious pain point in mathematical optimization. In the presentation, I intend to to describe the algorithms implemented, describe their use cases, and demonstrate their use to detect a modeling error in an optimization problem from chemical engineering.