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 constrast 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:

• The v0.6 release of ConstraintProgrammingExtensions.jl. Highlights of the ConstraintProgrammingExtensions.jl package include:
  • set definitions for dozens of constraint types
  • a number of bridges, including many bridges to convert constraint programming models into standard mixed-integer programming models
  • Support for the FlatZinc file format, a standard in constraint programming to exchange models (similar to the LP and MPS formats for linear programming)
• Interfacing several solvers through ConstraintProgrammingExtensions.jl. These include:
  • The pure-Julia ConstraintSolver.jl
  • The industry standard IBM CPLEX CP Optimizer
  • The open-source Chuffed

  Other pure-Julia constraint solvers have been released, but they do not yet use ConstraintProgrammingExtensions API:

  • JuliaConstraints
  • SeaPearl
• A session on constraint programming talks at JuMP-dev 2021
  • The design of MiniZinc
  • ConstraintProgrammingExtensions.jl
  • ConstraintSolver.jl
  • JuliaConstraints

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.

Twitter  facebook  Email