An update on constraint programming in JuMP


Author: Thibaut Cuvelier (@dourouc05)

JuMP and MathOptInterface are oriented towards traditional mathematical optimization, encompassing problem classes such as mixed-integer linear programs and conic optimization. However, the MathOptInterface API is amenable to other kinds of formalism, including constraint programming.

In contrast to linear or conic programs, constraint programs typically have no objective function, but a much wider variety of constraints that are supported. The best-known constraint is probably all_different, which models the fact that several integer-valued variables should take different values (i.e., no two variables are allowed to have the same value). However, there are a range of other constraint types, with a focus on describing combinatorial structures. Efficient solvers have been written for constraint programs.

There are a few tools for constraint programming outside the Julia ecosystem. The most popular are MiniZinc and OR-Tools.

The goal of the ConstraintProgrammingExtensions.jl package is to bring first-class support for constraint programming to JuMP and MathOptInterface.

Discussions about constraint programming support in the JuMP ecosystem started in 2019. The original scope was quite limited, as it only planned to propose some modeling capabilities to JuMP. However, quite soon, it morphed into a larger proposal of a full constraint programming environment, accessible from the same API as JuMP, including wrapping various specialized constraint programming solvers.

In the last few months, the constraint programming ecosystem in JuMP has made tremendous progress. Highlights include:

This is the start of our journey towards constraint programming in JuMP. Although MathOptInterface and JuMP are nearing their 1.0 release, the constraint programming ecosystem has still a long way to go. In the near term, more modelling features should be added as extensions to JuMP and more solvers should be made accessible. In the longer term, constraint programming modelling will also benefit from the next generation of nonlinear support.