Cerberus: A solver for mixed-integer programs with disjunctions
2021-07-30, 19:30–19:40 (UTC), JuMP Track

Disjunctive programming (DP) is a powerful framework for modeling complex logic in optimization problems. In this talk, we present Cerberus, a prototype MIP solver that treats disjunctive constraints as first-class objects.


Typically, DP problems are reformulated as mixed-integer programming (MIP) problems, and then passed to a MIP solver. Crucially, the MIP solver only receives this "flattened" MIP reformulation, and not the original, rich DP structure. We discuss how this structural information can be used within a LP-based branch-and-cut algorithm for dynamic reformulation and domain propagation without breaking incremental LP solves, a crucial ingredient for the success of modern solvers. We focus in particular on how the JuMP ecosystem facilitates the rapid development of such a solver which is heavily dependent on advanced functionality from the both the underlying solvers and the modeling interface.