CBCSolver: bound in root node differs significantly in versions 2.0.0, 2.1.0, 2.2.2, 2.3.0

[svigerske]

Issue created by migration from Trac.

Original creator: tfahle

Original creation time: 2009-08-26 14:39:23

Assignee: somebody

Version:

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:
||CBC 2.0.0|| 195.305 ||(14 row cuts (6 active), 28 column cuts)||
||all others|| 160.236||(0 row cuts (0 active), 0 column 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.

[svigerske]

Attachment testfile.zip by tfahle created at 2009-08-26 14:40:03

[svigerske]

Attachment COIN_PROBING.txt.txt by tfahle created at 2009-08-26 14:41:33

[svigerske]

Comment by tfahle created at 2009-08-26 15:26:49

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.

[svigerske]

Comment by tfahle created at 2009-08-27 09:23:45

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

[svigerske]

Different code gives different bounds. That's no bug.
Closing as no activity for almost 10 years.