Constraint Solver Part 12: Documentation and small changes

Creation date: 2019-10-25

Tags: julia, constraint-programming, optimization

Series: Constraint Solver in Julia

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!
```

will create:

Docs

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 only needs to be created once so in my case only on linux with v1.2.0 of Julia.

Once you have enabled GitHub actions there is a hidden secret secrets.GITHUB_TOKEN so you don't have to do anything there.

Currently it only works if you are using the master branch of Documenter.jl which means that instead of ] add Documenter you should use ] add Documenter.jl#master. This will be done in the docs folder after you did ] activate . to add it to the requirements of the docs folder.

This time you should make sure that you also push the Manifest.toml of the docs folder to the repository. This is needed as GitHub Actions should also use the master branch of Documenter.

You also have to add your own repository to the docs folder. This can be done by ] dev .. when you're still in the ] activate . stage.

In summary:

$ cd MY_REPO/docs
$ julia
> ] activate .
> ] add Documenter.jl#master
> ] dev ..

For Travis you would need to create a DOCUMENTER_KEY using Documenter.jl. This is not needed with GitHub Actions.

I want to thank Fredrik Ekre here as he helped me a lot to set this up for my ConstraintSolver repo.

Benchmarking

In this section I want to do some benchmarking of what is implemented so far. Comparison with other constraint solvers, specialized solvers and different kind of general solvers.

Sudoku

Update for sudoku since the last time I benchmarked it:

Sudoku

There are definitely some changes which makes solving the sudoku puzzles slower. I'll also dive into this. It's still faster than norvig and OR-Tools but if it's possible to get back to the previous speed we should probably do it.

Killer sudoku

As mentioned in the corresponding post I misunderstood the rules of killer sudoku (or just didn't read them til the end). Therefore this is split into two results.

  1. Killer sudoku without the constraint that a colored region (cage) also has the all different constraint

Killer sudoku special rules

  1. Real killer sudoku with that constraint

Killer sudoku normal rules

You can find the killer sudokus here.

This seems like there might be some performance improvements for the sum constraint or general improvements possible. The all different constraint in general is based on some results in normal rules and in normal sudoku better faster than OR-Tools.

Here it might also be the case that all different is slow in general because of the graph theory step but quite helpful. Maybe there is a way to decide whether that extra graph coloring step probably yield some new information or not.

Graph coloring

I did a small benchmark against the Cbc MIP solver last time. I wanted to test it against two other MIP solvers as well. Unfortunately it's a bit strange that the benchmark from last time and from this time are quite a bit different. On Thursday (24.10.2019) there was an update to Cbc.jl which is an update to the Cbc binaries v2.10.3 which might explain the differences.

I used the following julia versions:

Graph coloring benchmark

where one can clearly see that GLPK is much slower than the other two MIP solvers.

Graph coloring benchmark without GLPK

This constraint solver is definitely the fastest.

How about comparing it to Google OR-Tools?

Graph coloring ConstraintSolver vs OR-Tools

One can clearly see that the performance drops much quicker with the current implementation of our constraint solver than OR-Tools.

I think that can be improved by finding a feasible solution first using primarily depth first search and from the maximum depth take the one which has the best bound and if a feasible solution was found change to the current strategy which is: Optimize for best bound and if same best bound then take the one with highest depth. Will check it out issue #39.

I tried to run graph coloring on some random graphs and failed miserably. It takes forever. I'll analyse it and get back to you ;)

Rename the package?

Shell I rename the package to something else?

or what to you think about the current name. Would love to hear your thoughts.

You can comment on this issue #40

What's next?

There are some things missing:

The next post is up: How to profile julia code?

Stay tuned ;)

And as always:

Thanks for reading and special thanks to three patrons!

List of patrons paying more than 2$ per month:

I'm very happy for the support I get via Patreon and comments on reddit, HackerNews and Twitter. Would like to make this blog faster as the CMS doesn't turn out to be the best. When I reach my next goal of 50$ per month I'll create a faster blog which will also have a better layout:

If you have ideas => Please contact me!

If you want to support me and this blog please consider a donation via Patreon or via GitHub to keep this project running.

For a donation of a single dollar per month you get early access to the posts. Try it out for the last two weeks of October for free and if you don't enjoy it just cancel your subscription.

If you have any questions, comments or improvements on the way I code or write please comment here and or write me a mail o.kroeger@opensourc.es and for code feel free to open a PR on GitHub ConstraintSolver.jl

I'll keep you updated on Twitter OpenSourcES as well as my more personal one: Twitter Wikunia_de



Want to be updated? Consider subscribing on Patreon for free
Subscribe to RSS
© Ole Kröger. Last modified: June 09, 2020. Website built with Franklin.jl.