Re: [Help-glpk] glpk 4.65 release information
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
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] glpk 4.65 release information
Hi Chris, > In order to test the release, I tried the 2010 MIPLIB benchmark set, > calling glpsol with "--pcost --cuts" and a two hour time limit. The > final result is in the attached file, but the quick summary is that 20 > problems from this set were solved, while there were three aborts. Thank you very much for your efforts. I think your results are very useful. 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. Best regards, Andrew Makhorin > > > Of the three aborts, problem mspp16 just run out of memory, while > problems msc98-ip and ns1688347 failed in the primal simplex. > > > Specifically, msc98-ip failed with: > > Warning: numerical instability (dual simplex, phase II) > Warning: dual simplex failed due to excessive numerical instability > Assertion failed: teta_lim >= 0.0 > Error detected in file simplex/spxprim.c at line 665 > > while ns1688347 failed with: > Error: basis matrix is singular to working precision (cond = 3.07e+18) > Assertion failed: teta_lim >= 0.0 > Error detected in file simplex/spxprim.c at line 665 > > > > > Best Regards, > > > Chris Matrakidis > ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
