ConstraintSolver.jl v0.1.0

I confess that while I’m writing this it isn’t actually a package yet and I plan to publish this post to my Patrons today. One day before it will be a release (if nobody has any problem with it :D).

Edit: (7th of April) It now is an official package 🙂
You can install it with:

] add ConstraintSolver

Jump to the GitHub Repo

You’re new? Welcome to OpenSourc.ES and a long journey about: How to build a constraint solver?

• Start here and in a few weeks you can read this one 😀

Haven’t posted here for quite a while as I worked on the Covid19 visualization and did some other stuff during quarantine time. Had a look back into what I promised to write about and feel more and more the urge to use a new blog to have a better structure and a search function. Hopefully there will be a first working version in the next months. I already have one version with a very limited number of posts for my Patrons and writing new posts there first and transfer them over to the old one.

Anyway I found that I wanted to talk a bit about the general structure again using Multiple Dispatch. It is a talk about multiple dispatch in Julia. I more and more enjoy that feature. Well this post is not about multiple dispatch though but you should definitely watch the talk. I think post 20 (so the next one) will be about the general structure again which includes some dispatch things.

What the hell is this post about then?

Oh okay sorry I drifted away…
There were some issues/missing features I had before I wanted to release this basic version 0.1.0.

I’ll go through them one by one here and we’ll see how long this post will be.

• All solutions
• Branch splitting strategies
• Logging
• Registering v0.1.0

All solutions

I think I haven’t written about getting all solutions yet. I mentioned it at least three times before that this will be interesting for sudoku. Checking whether every sudoku has exactly one solution is also a nice feature if you want to create a sudoku puzzle yourself.

There are several options to implement this in the backend but the frontend side is what might be more interesting to you. In the backend I simply have a vector of vectors which saves every solution and I deactivate the early breaks in the backtrack functions to actually fully search the tree.

I have two options: all_solutions and all_optimal_solutions which are the same for feasibility problems and for optimization problems you might be only interested in optimal solutions but for small problems it might be nice to get all feasible solutions.

For the frontend you need to implement:

function MOI.get(model::Optimizer, ::MOI.ResultCount)
    return length(model.inner.solutions)
end

such that the user can query the number of solutions with: MOI.get(m, MOI.ResultCount()) when m is the model.
Additionally to get the actual solutions one needs to change the backend of…

Computing bounds

This is an ongoing series about: How to build a constraint solver?
It’s part 18 of the series so we have came a long way. In the last weeks you might have seen that I implemented a lot of stuff in between.
Since a few days ago I have a bigger project now: Visualizing the data we have about the new coronavirus COVID-19. I’ve made a blog post about it Visualizing COVID-19 but there are a lot of things to do to make it really useful. It was just a fast way of trying stuff out. I want to make it interactive and scale by population/population density/area as well as getting an idea of the likeliness to get infected in each country by combining those data.

Nevertheless I want to explain a major change in the ConstraintSolver in this post.

The problem

Last time I implemented the option to optimize on linear objectives. The problem is that I had only a very simple way of computing bounds. That means if we have the following problem:

m = Model(CS.Optimizer) 
@variable(m, 0 <= x[1:10] <= 15, Int)
@constraint(m, sum(x) <=  15)
@objective(m, Max, sum(x))

and run optimize!(m). It takes a crazy amount of time to proof that the optimal solution is 15. What I did so far was that the bound computation only works with the variables. That means we have a look at the maximum value of each variable and add them up to obtain a bound. Here it will be 150. With the additional constraint sum(x) <= 15. We can immediately reduce that to 15 but well the ConstraintSolver isn’t that intelligent.

My first idea was to use some knapsack heuristic for this and started programming and realized way too late that it’s not working for negative coefficients or negative values.

Then I tried to only use it for constraints where it actually works like the one above and someone opened an issue issue #83. It’s quite a good problem to see the next issue my approach had.

I’ll show the problem in a minute. First I want to explain the approach I had in a bit more detail. Every constraint had a function which had as an input the objective function and then I computed with the knapsack heuristic a bound based on each constraint and objective separately and used the tightest bound.

The problem is of course that I used each constraint individually instead of combining them:

Code from the mentioned issue:

using JuMP
using ConstraintSolver
const CS = ConstraintSolver

model = Model()

# Variables
@variable(model, 0 <= inclusion[h = 1:3] <= 1, Int);
@variable(model, 0 <= allocations[h = 1:3, a = 1:3] <= 1, Int);
@variable(model, 0 <= days[h = 1:3, a = 1:3] <= 5, Int);

# Constraints
@constraint(model, must_include[h = 1:3],
    sum(allocations[h,a] for a in 1:3) <= inclusion[h]
);
# at least n
@constraint(model, min_hospitals,
    sum(inclusion[h] for h in 1:3) >= 3
);
# every h must be...

Yeah some of you might wait for another post about the ConstraintSolver project but I needed a little bit of break this month.
There are some things I want to shortly mention in this post. It’s probably one for those of you who are interested in all kind of stuff that I’m working on and not a special topic.

I’ll talk about YouTube videos which includes the Mandelbrot set and two Enigma Videos and future projects. Afterwards I’m talking about the future of the blog and will have an extra section about a very fresh idea in my mind which I just want to put out there for now 😀

Before we start I should mention that my Enigma package is now official and can be installed with ] add Enigma. Juhu 🙂

YouTube videos

Let’s start with YouTube videos. For those of you who don’t follow me on Twitter or Patreon or the Enigma post at a later stage probably haven’t seen my YouTube videos.
I’ve created a YouTube channel a year ago and just posted some visualizations there for my Kaggle and sudoku posts. I thought that for some projects it might be nice to invest a bit more time in visualizing them and talking about it. I myself watch more YouTube videos than reading blog posts and probably more than I should.

I’m still going to blog more than I make YouTube videos for several reasons:

• You can copy and paste my code directly
• You can read it as fast or slow as you like
• You don’t have to deal with my accent (just with my writing style)
• I can edit stuff easily
• I can update my posts
• I can more easily link to other sources (yeah I can use the YT description)
• It feels like less work 😀

In general I think for coding projects blogging is the way to go. Nevertheless visualizing stuff is easier in videos.

For now I created three real videos:

• Enigma: Endless possibilities is not enough
• Coding the Mandelbrot Set in Julia (with GPU)
• How to crack the Enigma cipher?

Both Enigma videos are linked to my blog post about it. Where the first one is a simple explanation of how the machine works and the second one is about how to break the cipher if we just have a small clue about what the message might be about.

The video in between about the Mandelbrot set was just a simple idea I had one day where I wanted to do some “live” coding and thought the Mandelbrot set is a nice subject to visualize and do in such a session as it is easy to implement and I can use my GPU… finally 😀

In the video you see a clip zooming into the Mandelbrot set and then coding a still image of a Mandelbrot set using the CPU first and the speeding it up with the GPU. I might write a blog post about that project as…