Cerberus: A solver for mixed-integer programs with disjunctions

07/30/2021, 7:30 PM7:40 PM UTC
JuMP Track

Abstract:

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.

Description:

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.

Platinum sponsors

Julia Computing

Gold sponsors

Relational AI

Silver sponsors

Invenia LabsConningPumas AIQuEra Computing Inc.King Abdullah University of Science and TechnologyDataChef.coJeffrey Sarnoff

Media partners

Packt Publication

Fiscal Sponsor

NumFOCUS