Saturday September 24, 2005 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).
( Sep 24 2005, 06:06:29 PM CEST ) Permalink Comments [1]Found it!
Remember that I said I lost the sources of a project that I had been working on forever? Well.... I retrieved the sources this morning. I don't know if it is the latest version of the project, but the archive seems to date back from somewhere in 2004, and I can't remember having worked on it since a couple of years ago. So that sounds good, right?
It seems this version is still running, so I will make some modifications in order to print out the Mixed Integer Programming model. Sit tight...
( Sep 24 2005, 11:04:31 AM CEST ) Permalink Comments [0]