Re: [Help-glpk] glpk 4.65 release information

[Chris Matrakidis]

Hi Andrew,

I'd like to note that sometimes '--cuts' is not a best choice. For
example, air04 and air05 (hard set partitioning problems) from miplib
3.0 are solved quickly (about 10 mins on my machine) with '--pcost',
but with cutting planes the solution takes more 6 hours. Probably this
is because cutting planes increase fractionality of node subproblems.

I know, but on average they seem to help (at least for miplib).

There is another reason for this slowdown: MIR cut generation still takes a lot of time for some problems (even after the changes from two years ago). Some testing suggests that reducing the maximal number of rows that can be aggregated is not affecting the quality of generated cuts, but I haven't tested this as much as I would like.

Moreover, the second paper referenced in ios_process_cuts() [1] states "...we found that better overall results are typically obtained if separation is only invoked at each k-th backtracking (we choose k = 4 in our implementation)." Indeed, generating cuts after every fourth backtracking step seems to improve overall solver performance but again I haven't tested this as much as I would like.

Best Regards,

Chris Matrakidis

[1] Andreello, A.Caprara, and M.Fischetti, "Embedding Cuts in a Branch&Cut Framework: a Computational Study with {0,1/2}-Cuts", http://www.dei.unipd.it/~fisch/papers/012_branch_and_cut.pdf