Wilfred Thinking Aloud

Mixed Integer Programming

After I retrieved the sources of the piece of software that I've been blogging about during the last couple of days, I'm now also able to give away the Mixed Integer Programming models behind it. Explaining it all in detail would cause this entry to grow beyond a couple of pages, so I will stick to some examples.

Let's start with the tiles presented in the first figure. This case, Jummikub already generated an optimal solution, assuming that we want to maximize the number of tiles in the final solution. The next figure shows Jummikub's solution in case we're maximizing the total value of all tiles in the solution.

In the first case, the MIP model generated looks like this:

max: -d_red_01 -d_red_02 -d_red_03 -d_red_04 -d_red_05 -d_red_06 -d_red_07 -d_red_08 -d_red_09 -d_red_10 -d_red_11 -d_red_12 -d_red_13 -d_black_01 -d_black_02 -d_black_03 -d_black_04 -d_black_05 -d_black_06 -d_black_07 -d_black_08 -d_black_09 -d_black_10 -d_black_11 -d_black_12 -d_black_13 -d_yellow_01 -d_yellow_02 -d_yellow_03 -d_yellow_04 -d_yellow_05 -d_yellow_06 -d_yellow_07 -d_yellow_08 -d_yellow_09 -d_yellow_10 -d_yellow_11 -d_yellow_12 -d_yellow_13 -d_blue_01 -d_blue_02 -d_blue_03 -d_blue_04 -d_blue_05 -d_blue_06 -d_blue_07 -d_blue_08 -d_blue_09 -d_blue_10 -d_blue_11 -d_blue_12 -d_blue_13 +c_red_01 +c_red_02 +c_red_03 +c_red_04 +c_red_05 +c_red_06 +c_red_07 +c_red_08 +c_red_09 +c_red_10 +c_red_11 +c_red_12 +c_red_13 +c_black_01 +c_black_02 +c_black_03 +c_black_04 +c_black_05 +c_black_06 +c_black_07 +c_black_08 +c_black_09 +c_black_10 +c_black_11 +c_black_12 +c_black_13 +c_yellow_01 +c_yellow_02 +c_yellow_03 +c_yellow_04 +c_yellow_05 +c_yellow_06 +c_yellow_07 +c_yellow_08 +c_yellow_09 +c_yellow_10 +c_yellow_11 +c_yellow_12 +c_yellow_13 +c_blue_01 +c_blue_02 +c_blue_03 +c_blue_04 +c_blue_05 +c_blue_06 +c_blue_07 +c_blue_08 +c_blue_09 +c_blue_10 +c_blue_11 +c_blue_12 +c_blue_13;
r_1 -a_red_01 +a_red_02 > -0.0
r_2 -a_red_01 +a_red_03 > -0.0
r_3 -a_red_01 +a_red_02 > -0.0
r_4 -2.0 b_red_01 +b_black_01 +b_yellow_01 +b_blue_01 > -0.0
r_5 +a_red_01 +b_red_01 -d_red_01 -c_red_01 = 0.0
r_6 +c_red_01 < 0.0
r_7 -a_red_02 +a_red_03 > -0.0
r_8 +a_red_01 -a_red_02 +a_red_04 > -0.0
r_9 +a_red_01 -a_red_02 +a_red_03 > -0.0
...

Again, I don't have the time to explain it all in detail, but the thing to take away from this is that the number of available tiles of a certain type influences the factors and RHS's of the constraints (as far as I recall), and the strategy determines the function to optimize, which becomes pretty clear if you look at the different strategies offered in Jummikub:

The first strategy (maximizing the number of tiles in the solution, the solution in the first figure) is represented by the following goal function:

max: -d_red_01 -d_red_02 -d_red_03 -d_red_04 -d_red_05 -d_red_06
-d_red_07 -d_red_08 -d_red_09 -d_red_10 -d_red_11 -d_red_12 -d_red_13
-d_black_01 -d_black_02 -d_black_03 -d_black_04 -d_black_05
-d_black_06 -d_black_07 -d_black_08 -d_black_09 -d_black_10
-d_black_11 -d_black_12 -d_black_13 -d_yellow_01 -d_yellow_02
-d_yellow_03 -d_yellow_04 -d_yellow_05 -d_yellow_06 -d_yellow_07
-d_yellow_08 -d_yellow_09 -d_yellow_10 -d_yellow_11 -d_yellow_12
-d_yellow_13 -d_blue_01 -d_blue_02 -d_blue_03 -d_blue_04 -d_blue_05
-d_blue_06 -d_blue_07 -d_blue_08 -d_blue_09 -d_blue_10 -d_blue_11
-d_blue_12 -d_blue_13 +c_red_01 +c_red_02 +c_red_03 +c_red_04
+c_red_05 +c_red_06 +c_red_07 +c_red_08 +c_red_09 +c_red_10 +c_red_11
+c_red_12 +c_red_13 +c_black_01 +c_black_02 +c_black_03 +c_black_04
+c_black_05 +c_black_06 +c_black_07 +c_black_08 +c_black_09
+c_black_10 +c_black_11 +c_black_12 +c_black_13 +c_yellow_01
+c_yellow_02 +c_yellow_03 +c_yellow_04 +c_yellow_05 +c_yellow_06
+c_yellow_07 +c_yellow_08 +c_yellow_09 +c_yellow_10 +c_yellow_11
+c_yellow_12 +c_yellow_13 +c_blue_01 +c_blue_02 +c_blue_03 +c_blue_04
+c_blue_05 +c_blue_06 +c_blue_07 +c_blue_08 +c_blue_09 +c_blue_10
+c_blue_11 +c_blue_12 +c_blue_13;

The other strategy (maximizing the total value of tiles in the solution, the solution in the second figure) is represented by the following goal function:

max:
+c_red_012.0c_red_023.0c_red_034.0c_red_045.0c_red_056.0c_red_067.0c_red_078.0c_red_089.0c_red_0910.0c_red_1011.0c_red_1112.0c_red_1213.0c_red_13
+c_black_012.0c_black_023.0c_black_034.0c_black_045.0c_black_056.0c_black_067.0c_black_078.0c_black_089.0c_black_0910.0c_black_1011.0c_black_1112.0c_black_1213.0c_black_13
+c_yellow_012.0c_yellow_023.0c_yellow_034.0c_yellow_045.0c_yellow_056.0c_yellow_067.0c_yellow_078.0c_yellow_089.0c_yellow_0910.0c_yellow_1011.0c_yellow_1112.0c_yellow_1213.0c_yellow_13
+c_blue_012.0c_blue_023.0c_blue_034.0c_blue_045.0c_blue_056.0c_blue_067.0c_blue_078.0c_blue_089.0c_blue_0910.0c_blue_1011.0c_blue_1112.0c_blue_1213.0c_blue_13;

Hmmm, the second goal looks a little odd. I think this is a bug in the printing functionality of the LP solver that I'm using. Anyway, it's clear that there is a difference, right?

You can download the LP files here (first LP model) and here (second LP model).