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 --cuts --pcost,,,
Name, Dual Bound, Primal Bound, Gap%, Nodes, Time, Status, Solution
30n20b8,151,302,100,2607,3601, stopped, ok
acc-tight5,0,0,0,1,1, ok, ok
aflow40b,1122,1168,4.1,13795,3600, stopped, ok
air04,56137,56137,0,43945,2934, ok, ok
app1-2,-230,-41,461,13206,3603, stopped, ok
ash608gpia-3col,1.00E+20,1.00E+20,--,57,185, ok, --
bab5,-111665.934,-106411.84,4.9,357,3603, stopped, ok
beasleyC3,560,754,34.6,7484,3600, stopped, ok
biella1,3062607.68,3065005.78,0.1,1206,3606, stopped, ok
bienst2,54.6,54.6,0,216243,1454, ok, ok
binkar10_1,6742.20002,6742.20002,0,87877,891, ok, ok
bnatt350,0,0,0,1,1, ok, ok
core2536-691,688.779403,689,0,2364,3604, stopped, ok
cov1075,18,20,11.1,18985,3601, stopped, ok
csched010,369.901019,408,10.3,3849,3600, stopped, ok
danoint,63.9111228,65.667,2.7,55887,3600, stopped, ok
dfn-gwin-UUM,37900,38752,2.2,60429,3601, stopped, ok
eil33-2,934.007916,934.007916,0,4769,131, ok, ok
eilB101,1216.92017,1216.92017,0,71847,895, ok, ok
enlight13,28,71,153.6,42008,3600,
