RelationalAI sponsors constraint programming support in JuMP

announcements  · 

Author: Miles Lubin, Juan Pablo Vielma, Carleton Coffrin and Changhyun Kwon

The JuMP Steering Committee is pleased to announce that we, through NumFOCUS, have signed an agreement with RelationalAI to improve constraint programming support in JuMP.

Constraint programming is a goal of the post-1.0 JuMP roadmap, and we gave an update on our progress last year.

The three main goals of this new work are to officially integrate constraint programming sets into MathOptInterface, to provide maintained support for constraint programming solvers, and to write bridges from constraint programming sets into mixed-integer linear programming formulations.

We’re tracking the status of these goals in MathOptInterface.jl issue #1805.

The first person being funded is Dr. Oscar Dowson, a core contributor to JuMP, and also a member of the Steering Committee.

Work to-date

We have already made significant progress, adding the following ten new sets to MathOptInterface:

along with bridges from the sets to mixed-integer linear programming formulations.

Example

This work was released in MathOptInterface v1.6.0, so these sets are ready to use now in JuMP and MathOptInterface. Here’s an example using the AllDifferent set to solve a Sudoku puzzle with HiGHS:

using JuMP, HiGHS

function solve_sudoku(grid, optimizer)
    model = Model(optimizer)
    @variable(model, 1 <= x[1:9, 1:9] <= 9, Int)
    @constraint(model, [i = 1:9], x[i, :] in MOI.AllDifferent(9))
    @constraint(model, [j = 1:9], x[:, j] in MOI.AllDifferent(9))
    for i in (0, 3, 6), j in (0, 3, 6)
        @constraint(model, vec(x[i.+(1:3), j.+(1:3)]) in MOI.AllDifferent(9))
    end
    for i in 1:9, j in 1:9
        if grid[i, j] != 0
            fix(x[i, j], grid[i, j]; force = true)
        end
    end
    optimize!(model)
    return round.(Int, value.(x))
end

grid = [
    5 3 0 0 7 0 0 0 0
    6 0 0 1 9 5 0 0 0
    0 9 8 0 0 0 0 6 0
    8 0 0 0 6 0 0 0 3
    4 0 0 8 0 3 0 0 1
    7 0 0 0 2 0 0 0 6
    0 6 0 0 0 0 2 8 0
    0 0 0 4 1 9 0 0 5
    0 0 0 0 8 0 0 7 9
]

julia> solve_sudoku(
           grid,
           optimizer_with_attributes(HiGHS.Optimizer, "presolve" => "off"),
       )
9×9 Matrix{Int64}:
 5  3  4  6  7  8  9  1  2
 6  7  2  1  9  5  3  4  8
 1  9  8  3  4  2  5  6  7
 8  5  9  7  6  1  4  2  3
 4  2  6  8  5  3  7  9  1
 7  1  3  9  2  4  8  5  6
 9  6  1  5  3  7  2  8  4
 2  8  7  4  1  9  6  3  5
 3  4  5  2  8  6  1  7  9

MiniZinc.jl

We’ve also written and released the MiniZinc.jl package, which is an interface from JuMP to the MiniZinc modeling language.

MiniZinc supports a range of constraint programming solvers, and so you can solve the same Sudoku problem using the Chuffed constraint programming solver as follows:

using MiniZinc

julia> solve_sudoku(grid, () -> MiniZinc.Optimizer{Float64}(MiniZinc.Chuffed()))
9×9 Matrix{Int64}:
 5  3  4  6  7  8  9  1  2
 6  7  2  1  9  5  3  4  8
 1  9  8  3  4  2  5  6  7
 8  5  9  7  6  1  4  2  3
 4  2  6  8  5  3  7  9  1
 7  1  3  9  2  4  8  5  6
 9  6  1  5  3  7  2  8  4
 2  8  7  4  1  9  6  3  5
 3  4  5  2  8  6  1  7  9

Next steps

In addition to the work already completed, the work sponsored by RelationalAI will allow us to add support for reified constraints, improve the tutorials and documentation, and investigate ways that we can connect JuMP and MathOptInterface to boolean satisfiability solvers.

(Per our conflict of interest policy, Oscar, who is funded by the grant, recused himself from Steering Committee votes on this agreement.)