ConstraintSolver.jl

This package aims to be a constraint solver written in Julia and will be documented completely on my blog OpenSourc.es. There is of course also the general user manual here

Goals

• Easily extendable
• Teaching/Learning about constraint programming

Installation

You can install this julia package using ] add ConstraintSolver or if you want to change code you might want to use ] dev ConstraintSolver.

Example

You can easily use this package with the same modelling package as you might be used to for solving (non)linear problems in Julia: JuMP.jl.

Sudoku

using JuMP

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

using ConstraintSolver
# define a shorter name ;)
const CS = ConstraintSolver

# creating a constraint solver model and setting ConstraintSolver as the optimizer.
m = Model(CS.Optimizer) 
# define the 81 variables
@variable(m, 1 <= x[1:9,1:9] <= 9, Int)
# set variables if fixed
for r=1:9, c=1:9
    if grid[r,c] != 0
        @constraint(m, x[r,c] == grid[r,c])
    end
end

for rc = 1:9
    @constraint(m, x[rc,:] in CS.AllDifferentSet())
    @constraint(m, x[:,rc] in CS.AllDifferentSet())
end

for br=0:2
    for bc=0:2
        @constraint(m, vec(x[br*3+1:(br+1)*3,bc*3+1:(bc+1)*3]) in CS.AllDifferentSet())
    end
end

optimize!(m)

# retrieve grid
grid = convert.(Int, JuMP.value.(x))

Supported variables and constraints

You can see a list of currently supported constraints in the docs. This constraint solver works only with bounded discrete variables.

Blog posts

• Setup of the solver and basic backtracking for Sudoku
• Pruning in Sudoku
• More pruning and benchmarks
• Sophisticated implementation of the alldifferent constraint and benchmarks
• New data structure for better user interface and performance
• Backtrack without recursion and start of sum constraint
• Speed up the sum constraint
• UI changes and refactoring
• Recap video
• First step in graph coloring
• Comarison with MIP using graph coloring
• Documentation with Documenter.jl and newest Benchmarking results
• How to profile Julia code
• Second take on bipartite matchings
• Making it a JuMP solver
• Dealing with real objectives
• Support for linear objectives
• Table logging
• Bound computation
• v0.1.0
• Table Constraint
• Solving Str8ts
• Bugs & Benchmarks
• Indicator constraint
• Indicator constraint Part 2

Notice

I'm a MSc student in computer science so I don't have much knowledge on how constraint programming works but I'm keen to find out ;)

Support

If you find a bug or improvement please open an issue or make a pull request. You just enjoy reading and want to see more posts and get them earlier? Support me on Patreon or click on the support button at the top of this website. ;)