Series: Constraint Solver in Julia

• Part One: Setup and backtracking
• Part Two: Pruning
• Part Three: Pruning+Benchmarking
• Part Four: Alldifferent constraint
• Part Five: Better data structure
• Part Six: Sum constraint first part
• Part Seven: Sum constraint speed-up
• Part Eight: UI Refactoring
• Part Nine: Recap video
• Part Ten: First part of graph coloring
• Part Eleven: MIP graph coloring and optimization

This is part 12 of the series about: How to build a Constraint Programming solver?

It’s a bit different this time. This is a series and sometimes I make just small changes that I normally wouldn’t blog about.
In this series I want to post updates as frequently as possible to keep you updated.

In this post you can learn how to write a documentation to your Julia package. You can visit mine here: ConstraintSolver.jl documentation.

Additionally a contributor made a small change to speed up the graph coloring example. I will add an update on benchmarks on sudoku, killer sudoku with only a handful of test cases as it’s time consuming to create them by hand as well as benchmarks on Graph Coloring in comparison to Google OR-Tools and some more MIP solvers (Cbc.jl and Gurobi.jl).

Then we know how fast this solver is and can either focus on performance in some cases or keep building forward by creating other constraints and objectives as the amount is still quite limited.

Creating a documentation

I use Documenter.jl for creating a documentation.

There are only some things that I think are important for you which I didn’t see directly in the documentation.

For creating a documentation using Travis you can completely rely on on the documentation of Documenter.jl.

In general it creates a docs folder in your repository and you can write a normal markdown documentation but also be able to use the code documentation of functions from your code i.e

## User interface functions

``@docs
ConstraintSolver.init
add_var!
``

<- should be ““`” (3 of them) but my markdown can’t handle it :/

will create:

and will be updated whenever you change the function documentation in your code i.e

"""
    init()

Initialize the constraint model object
"""
function init()

Now to publish this directly on GitHub pages one needs to set
Repo-> Settings – GitHub Pages to gh-pages (might get activated later as you currently don’t have this branch.)

The html code needs to be created from your markdown files and either Travis can do this or for this case GitHub Actions.

For this you can create a new .yml file in the .github/workflows folder. A new file there represents a new GitHub Actions workflow.
I call mine docs.yml and it contains:

name: Documentation

on: [push, pull_request]

jobs:
  build:
    runs-on: ${{ matrix.os }}
    strategy:
      matrix:
        julia-version: [1.2.0]
        julia-arch: [x86]
        os: [ubuntu-latest]
    steps:
      - uses: actions/checkout@v1.0.0
      - uses: julia-actions/setup-julia@latest
        with:
          version: ${{ matrix.julia-version }}
      - name: Install dependencies
        run: julia --project=docs/ -e 'using Pkg; Pkg.instantiate()'
      - name: Build and deploy
        env:
          GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
        run: julia --project=docs/ docs/make.jl

The documentation…

Series: Constraint Solver in Julia

• Part One: Setup and backtracking
• Part Two: Pruning
• Part Three: Pruning+Benchmarking
• Part Four: Alldifferent constraint
• Part Five: Better data structure
• Part Six: Sum constraint first part
• Part Seven: Sum constraint speed-up
• Part Eight: UI Refactoring
• Part Nine: Recap video
• Part Ten: First part of graph coloring

This is part 11 of the series about: How to build a Constraint Programming solver?

In the last post we created the != constraint to solve graph coloring. The problem is that we currently can’t specify that we want to minimize the number of colors used. We therefore tried it out with four colors because based on the four color theorem this should work and well it did. After that we checked whether that is the best solution by removing the fourth color. It turned out to be infeasible.

I want to add the possibility to optimize in this post. We have to keep track of a bit more information for this which we will do first before implementing the optimization step.

First of all I want to show you another interesting way to solve graph coloring using Mixed Integer Programming (MIP). I did a series on how to solve linear problems (see Simplex Method) and also a post on how to use a MIP solver to solve small Travelling Salesman Problems TSP solver.

Where the later one is currently out dated as it uses an older version of JuMP.jl and Julia itself.

Comparison with MIP

Let’s compare our current constraint solver approach without optimization step with a MIP approach. We will use GLPK.jl which is a wrapper to call GLPK in Julia. It works using JuMP.jl which is the Julia package for mathematical programming.

I got the idea from this blog post on graph coloring written in R.

What are the rules? Or how can we write the graph coloring problem as a mixed integer (here actually all variables are integer) linear problem?

We could use the same variable structure:

• A variable for each state having the possible values 1,2,3 & 4

but it’s not that easy to have a != in a linear problem.
Therefore we use a different approach namely we have four binary variables for each state. If we don’t know the four color theorem we need to add more colors same is true if we don’t actually have a valid 2D Map. Graph coloring can also be used if we have a graph of nodes and edges we want to separate the nodes in such a way that two connected nodes don’t have the same color.

Pseudocode:

c[s][1,2,3,4] = {0,1}

c[1][1] = 1 would mean that we use color 1 (red) for the state of Washington which was the first in our list of states.

The first constraint then is quite obvious

\[
\sum_{i=1}^4 c[s][i] = 1 \quad \forall s \in \text{States}\]

Meaning: Each state has exactly one color.

Now we also want to minimize the number of colors we use….