Minizinc for Constrained Optimisation Problems
Minizinc for Constrained Optimisation Problems
Minizinc is a convenient and easy-to-use constraint programming (CP) modelling language that I first came across by way of a university course. However, outside of the realm of scheduling, packing, and whatever other optimisation problems that (don’t really) come across in everyday life, I seldom had chances to use this technology. That is, until I discovered…
Jane Street uploads monthly puzzles. They can be reasonably enjoyable to solve though they can be fairly tricky as well. More importantly, many of the puzzles posted there lend themselves to such optimiser tools.
Below, I have a small collection of some problems I’ve managed to solve with Minizinc. (I haven’t attempted too many… working full time is hard!)
Puzzles
Knight Moves 6
The first puzzle I cracked after briefly attempting the previous month’s. The key insight here is that in the recursive backtrack search, searching backwards is advantageous because significant parts of the otherwise broad search tree may be pruned as the inverse operation of multiplication – division must result in integers, which is far more constraining than constraints that are possible to write when looking forward.
Here’s a Minizinc model that can solve the problem:
include "globals.mzn";
var 1..47: a;
var 1..47: b;
var 1..47: c;
constraint all_different([a, b, c]);
array [1..6, 1..6] of var 1..47: grid = [|
a, b, b, c, c, c |
a, b, b, c, c, c |
a, a, b, b, c, c |
a, a, b, b, c, c |
a, a, a, b, b, c |
a, a, a, b, b, c |
|];
var 1..36: len1;
array[1..36] of var 1..6: rows1;
array[1..36] of var 1..6: cols1;
% Start finish constraint
constraint rows1[1] = 6 /\ cols1[1] = 1;
constraint rows1[len1] = 1 /\ cols1[len1] = 6;
% Knight-like constraint
constraint forall (i in 1..(len1-1)) (
exists (j in {-2, 2}, k in {-1, 1}) (
(rows1[i] + j = rows1[i+1] /\ cols1[i] + k = cols1[i+1]) \/
(rows1[i] + k = rows1[i+1] /\ cols1[i] + j = cols1[i+1])
)
);
% No repeat constraint
constraint all_different([rows1[i] * 6 + cols1[i] | i in 1..len1]);
% Score constraint
array[1..36] of var 1..2024: scores1;
constraint scores1[1] = 1 /\ scores1[len1] = 2024;
constraint forall (i in 2..len1) (
scores1[i] =
if (grid[rows1[i-1], cols1[i-1]] = grid[rows1[i], cols1[i]])
then (scores1[i-1] + grid[rows1[i], cols1[i]])
else (scores1[i-1] * grid[rows1[i], cols1[i]])
endif
);
var 1..36: len2;
array[1..36] of var 1..6: rows2;
array[1..36] of var 1..6: cols2;
% Start finish constraint
constraint rows2[1] = 1 /\ cols2[1] = 6;
constraint rows2[len2] = 6 /\ cols2[len2] = 1;
% Knight-like constraint
constraint forall (i in 1..(len1-1)) (
exists (j in {-2, 2}, k in {-1, 1}) (
(rows2[i] + j = rows2[i+1] /\ cols2[i] + k = cols2[i+1]) \/
(rows2[i] + k = rows2[i+1] /\ cols2[i] + j = cols2[i+1])
)
);
% No repeat constraint
constraint all_different([rows2[i] * 6 + cols2[i] | i in 1..len2]);
% Score constraint
array[1..36] of var 1..2024: scores2;
constraint scores2[1] = 1 /\ scores2[len2] = 2024;
constraint forall (i in 2..len2) (
scores2[i] =
if (grid[rows2[i-1], cols2[i-1]] = grid[rows2[i], cols2[i]])
then (scores2[i-1] + grid[rows2[i], cols2[i]])
else (scores2[i-1] * grid[rows2[i], cols2[i]])
endif
);
solve minimize a+b+c;
Output:
a = 22;
b = 2;
c = 44;
len1 = 5;
rows1 = [6, 5, 3, 2, 1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 6, 1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6];
cols1 = [1, 3, 2, 4, 6, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 6, 5, 4, 5, 5, 2, 5, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5];
scores1 = [1, 23, 45, 1980, 2024, 1, 1, 1, 1, 1, 1, 1, 2024, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2022, 2024];
len2 = 6;
rows2 = [1, 3, 2, 4, 2, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6];
cols2 = [6, 5, 3, 2, 1, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6];
scores2 = [1, 45, 90, 1980, 2002, 2024, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2024, 2024, 1, 1, 1, 1, 1, 2024, 1, 1, 1, 1981, 2024];
_objective = 68;
----------
...
----------
a = 1;
b = 3;
c = 2;
len1 = 17;
rows1 = [6, 5, 4, 2, 3, 4, 5, 3, 5, 6, 4, 5, 6, 4, 3, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 6, 1, 1, 2, 3, 1, 6, 1, 1];
cols1 = [1, 3, 5, 6, 4, 6, 4, 3, 2, 4, 3, 1, 3, 4, 2, 4, 6, 1, 1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 4, 3, 4, 6, 6];
scores1 = [1, 2, 4, 6, 18, 36, 108, 111, 111, 333, 336, 336, 337, 1011, 1011, 2022, 2024, 22, 23, 1, 1, 2024, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2023, 2024];
len2 = 20;
rows2 = [1, 2, 3, 5, 6, 4, 2, 1, 3, 5, 6, 5, 4, 6, 5, 3, 1, 3, 1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6];
cols2 = [6, 4, 2, 3, 5, 4, 3, 5, 4, 5, 3, 1, 3, 2, 4, 3, 4, 1, 1, 1, 6, 5, 6, 3, 6, 6, 6, 6, 6, 6, 3, 3, 6, 6, 6, 6];
scores2 = [1, 3, 3, 4, 12, 15, 18, 36, 108, 111, 111, 112, 336, 336, 1008, 1011, 2022, 2022, 2023, 2024, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 22, 1, 1, 1, 2023, 2024];
_objective = 6;
----------
==========
Finished in 2m 23s.
Finding the optimal solution of A=2 B=3 C=1 (A+B+C=6), and two satisfactory paths for the knights.
Sum of Squares
After enlisting a friend’s help for December’s riddle, we decided that it was pretty fun, and that we should look back in the archive. This is the first ever archived puzzle, and frankly no match for today’s CP solver technology.
array[1..5, 1..5] of var 0..9: answer;
constraint answer[2, 5] mod 2 = 0;
constraint sum(answer[3, 1..5]) mod 3 = 0;
constraint (answer[4, 4] * 10 + answer[4, 5]) mod 4 = 0;
constraint answer[5, 5] mod 5 = 0;
constraint sum(answer[1..5, 1]) mod 6 = 0;
constraint (answer[1, 2] * 10000 +
answer[2, 2] * 1000 +
answer[3, 2] * 100 +
answer[4, 2] * 10 +
answer[5, 2]) mod 7 = 0;
constraint (answer[3, 3] * 100 + answer[4, 3] * 10 + answer[5, 3]) mod 8 = 0;
constraint sum(answer[1..5, 4]) mod 9 = 0;
constraint answer[5, 5] = 0;
solve maximize sum(answer);
Output:
answer =
[| 9, 9, 9, 0, 9
| 9, 9, 9, 0, 8
| 0, 0, 6, 0, 0
| 9, 9, 9, 0, 8
| 9, 9, 6, 0, 0
|];
_objective = 136;
----------
...
----------
answer =
[| 8, 8, 9, 9, 9
| 9, 9, 9, 9, 8
| 7, 9, 8, 9, 9
| 9, 9, 8, 9, 6
| 9, 9, 8, 9, 0
|];
_objective = 205;
----------
==========
Hooks
I raced my friend on who could solve it faster. He was doing it by hand and I was writing a CP model. (I won).
include "globals.mzn";
array[1..9, 1..9] of var 0..9: answer;
% Each "hook" needs to have the right number, or 0
constraint forall (i, j in 1..9) (
answer[i, j] = 0 \/
answer[i, j] = max(i, j)
);
array[1..9] of int: row_sums = [26, 42, 11, 22, 42, 36, 29, 32, 45];
constraint forall (i in 1..9) (sum(answer[i, 1..9]) = row_sums[i]);
array[1..9] of int: col_sums = [31, 19, 45, 16, 5, 47, 28, 49, 45];
constraint forall (i in 1..9) (sum(answer[1..9, i]) = col_sums[i]);
constraint forall (n in 1..9) (among(n, answer, {n}));
Output:
answer =
[| 1, 0, 3, 0, 0, 6, 7, 0, 9
| 2, 2, 3, 0, 5, 6, 7, 8, 9
| 3, 0, 0, 0, 0, 0, 0, 8, 0
| 4, 4, 4, 4, 0, 6, 0, 0, 0
| 5, 5, 5, 5, 0, 6, 7, 0, 9
| 0, 0, 6, 0, 0, 6, 7, 8, 9
| 7, 0, 7, 7, 0, 0, 0, 8, 0
| 0, 8, 8, 0, 0, 8, 0, 8, 0
| 9, 0, 9, 0, 0, 9, 0, 9, 9
|];
Special Mention: Altered States
The goal here is to place letters in a grid so that you can trace out the names of the states in the US. As far as I know, an optimal solution for this problem is still yet to be found. I managed to find a high-scoring grid by directly using one of the underlying solvers used by Minizinc called CP-SAT by Google’s OR-Tools.
Learning how to use CP-SAT was fairly painless thanks to having used Minizinc before, and by scoring 123 points, I got my name as a special mention on the solutions page!
Here’s the model.
NB: The solution was found by using a sizeable amount of compute. Specifically, a number of machines were running solvers and restarting the solving process about once an hour. In total, due to the random nature of the optimisation process, finding this solution took days and costed thousands of CPU hours.