Re: [Help-glpk] glpk 4.65 release information

[Chris Matrakidis]

Hi Andrew,

A few weeks ago you wrote:

I'd like to note that sometimes '--cuts' is not a best choice.

I did an experiment regarding this. In particular, I tried 84 out of the 87 problems in the miplib 2010 benchmark set (the other 3 needed more than an hour to solve the root relaxation). I provided the optimal solution in every (feasible) case to make sure no unnecessary nodes were searched (and disabled the rounding heuristic to save some time). Then did three runs with a time limit of 1 hour per problem and pcost branching: with cuts, without cuts and with cuts added every fourth backtracking step. The problems solved for the three cases were 25, 21 and 23 respectively.

The results are summarised in the following table (which I hope is readable). The numbers in parentheses are the average execution time or gap compared to the other case, so in the 3 cases where A is faster with an average of 56% means they executed in 56% of the time B took (i.e. lower is better).

+-------+-------+--------+--------+--------+--------+--------+---------+---------+
|   A   |   B   |  both  | only A | only B |    A   |    B   |  gap A  |  gap B  |
|       |       | solved | solved | solved | faster | faster | smaller | smaller |
+-------+-------+--------+--------+--------+--------+--------+---------+---------+
| with  |  w/o  |   19   |    6   |    2   |    3   |   12   |    24   |    19   |
|  cuts |  cuts |        |        |        |  (56%) |  (52%) |  (61%)  |  (76%)  |
+-------+-------+--------+--------+--------+--------+--------+---------+---------+
|  w/o  | every |   20   |    1   |    3   |   11   |    5   |    15   |    27   |
|  cuts |   4   |        |        |        |  (65%) |  (71%) |  (75%)  |  (59%)  |
+-------+-------+--------+--------+--------+--------+--------+---------+---------+
| every |  with |   22   |    1   |    3   |   13   |    4   |    23   |    17   |
|   4   |  cuts |        |        |        |  (72%) |  (87%) |  (85%)  |  (84%)  |
+-------+-------+--------+--------+--------+--------+--------+---------+---------+

The situation was very different using the modifications I published earlier. The problems solved were now 38, 40 and 43 for the same three cases respectively. Now without cuts more problems are solved within the time limit than with cuts, which I wasn't expecting. However even more problems are solved by adding cuts every fourth backtracking step. Again the following table has more details.


+-------+-------+--------+--------+--------+--------+--------+---------+---------+

|   A   |   B   |  both  | only A | only B |    A   |    B   |  gap A  |  gap B  |
|       |       | solved | solved | solved | faster | faster | smaller | smaller |
+-------+-------+--------+--------+--------+--------+--------+---------+---------+
| with  |  w/o  |   32   |    6   |    8   |    3   |   25   |    16   |    12   |
|  cuts |  cuts |        |        |        |  (40%) |  (51%) |  (42%)  |  (61%)  |
+-------+-------+--------+--------+--------+--------+--------+---------+---------+
|  w/o  | every |   36   |    4   |    7   |   23   |    9   |    7    |    19   |
|  cuts |   4   |        |        |        |  (59%) |  (61%) |  (71%)  |  (46%)  |
+-------+-------+--------+--------+--------+--------+--------+---------+---------+
| every |  with |   37   |    6   |    1   |   27   |    4   |    17   |    12   |
|   4   |  cuts |        |        |        |  (63%) |  (63%) |  (68%)  |  (74%)  |
+-------+-------+--------+--------+--------+--------+--------+---------+---------+

I think this change in behaviour with my modifications is due to restoring the root node less during the search, and consequently requiring fewer factorisations.

I'm attaching csv files with the results of the runs if you want to see more details.

Best Regards,

Chris Matrakidis

glpk_4.65.csv
Description: Text Data

glpk_4.65_mod.csv
Description: Text Data