s-c-e
commented
5 years ago Mail from John Forrest:
Techniques such as probing can be very expensive and default settings have been changed between versions. What happens if you try and force more probing e.g. -probing forceonstrong?
Testresults in details call: cbcSolve testfile.mps -cuts off -probing on|forceOnStrong -branch
results in Initial Lower Bound 160.236, optimal solution 246.296 (all versions)
Bound improvement in Root node:
| CBC 2.0.0 | probing on | LB: 195.305 | 14 row cuts, 6 active, 28 col cuts |
|---|---|---|---|
| probing forceOnStrong | LB: 245.235 | 720 row cuts, 33 active, 44 colcuts | |
| CBC 2.1.0 | probing on | LB: 215.421 | 104 row cuts, 12 active, 41 col cuts |
| probing forceOnStrong | LB: 245.235 | 823row cuts, 43 active, 45 col cuts | |
| CBC 2.2.2 | probing on | LB: 160.236 | 0 row cuts, 0 active, 0 col cuts |
| probing forceOnStrong | LB: 160.236 | 0 row cuts, 0 active, 0 col cuts | |
| CBC 2.3.0 | probing on | LB: 160.236 | 0 row cuts, 0 active, 0 col cuts |
| probing forceOnStrong | LB: 160.236 | 0 row cuts, 0 active, 0 col cuts |
all tests under WinXP using Visual Studio 2005 in debug mode
Attachment: https://github.com/s-c-e/cbc-trac-migration-attachments/blob/master/trac-ticket-78.zip
We ran cbcSolver on Windows using Visual Studio2005 on a testproblem and recogniced different initial bounds after cuts.
In the default setting, CBC 2.1.0 delievers the best bound, followed by CBC 2.0.0. CBC 2.2.2 and 2.3.0 cannot improve the bounds significantly by cuts. In CBC 2.0.0 only probing cuts are active, all other versions use a mix of cuts.
Using only probing cuts CBC 2.0.0 is best, all other versions cannot improve the LP bound at all.
This result looks like there is a problem in probing cuts.
However, parameter tuning for probing cuts allows to improve the bound of cbcSolve 2.1.0, whereas 2.2.2 and 2.3.0 are not affected by the tuning.
On the other hand, when using a small driver that reads the mps, adds probing and calls branchandbound afterwards, no CBC version can improve bounds.
This gives the impression that cbcSolve uses some more setting that improves probing efficiency in version 2.0.0 and 2.1.0, whereas the setting is missing or changed in versions 2.2.2 and 2.3.0
====
Detailed results
The testfile has an LP bound of 160.236 and an optimal IP bound of 246.296
calling: cbcSolve testfile.mps -branch
we get the following bounds in root node after adding cuts:
CBC 2.0.0 195.305 CBC 2.1.0 221.561 CBC 2.2.2 and 2.3.0 160.296, i.e. bound remains almost unchanged
In order to isolate the effect, we tried with probing cuts only:
calling: cbcSolve testfile.mps -cuts off -probing on -branch we get the following bounds in root node after adding only probing cuts:
That is: Probing cuts are no longer effective on our input file in CBC 2.1.0 - 2.3.0
It should be noted that the preprocessed model already differs in size:
CBC 2.0.0 588 rows, 494 columns (364 integer) and 3441 elements CBC 2.1.0 585 rows, 488 columns (364 integer) and 3435 elements CBC 2.2.2 and 2.3.0 585 rows, 466 columns (342 integer) and 3413 elements
So we switched of preprocessing
calling: cbcSolve testfile.mps -cuts off -probing on -preprocess off -presolve off -branch
we obtain a bound of 206.922 in CBC 2.0.0, all other versions do not improve the root bound.
Tracking down things a bit further, we found that cbcSolve.cpp changed some probing parameters when going from version 2.0.0 to 2.1.0. and later So we changed the source code of cbcSolve.cpp such that all probing generators use the same large parameter setting: maxPass=30, maxPassRoot=30, maxProbe=100, maxProbeRoot=500, maxLook=100, maxLookRoot=100, maxElements=2000.
calling: cbcSolve testfile.mps -cuts off -probing on -branch
we get the following bounds in root node after adding cuts:
CBC 2.0.0 and 2.1.0 246.236 CBC 2.2.2 and 2.3.0 160.296
It seems that 2.1.0 can be tuned to produce a tighter bound when only using probing, whereas versions 2.2.2 and 2.3 cannot.
However, a test with a very simple driver (derived from sample1.cpp and attached to this report) shows that the difference is not (only) in probing. There must be some more effects, as the simple driver that reads the mps file, adds a probing cut generator with the same parameter setting as above gives a root bound of 160.236 in all tested versions.
Please find attached the (zipped) mps file and a txt file containing parts of the logfiles of all runs. Also attached is the simple driver.
All tests were performed using MS Visual Studio 2005 on an Intel QuadCore? CPU using Debug mode. There are numerical differences between release and debug version in this setting. I hope the effect is nevertheless still reproducible.