Opened 10 years ago

Closed 7 weeks ago

#78 closed defect (migrated)

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

Reported by: tfahle Owned by: somebody
Priority: major Component: component1
Version: Keywords:
Cc:

Description

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.

Attachments (2)

testfile.zip (29.2 KB) - added by tfahle 10 years ago.
COIN_PROBING.txt.txt (9.2 KB) - added by tfahle 10 years ago.

Download all attachments as: .zip

Change History (5)

Changed 10 years ago by tfahle

Changed 10 years ago by tfahle

comment:1 Changed 10 years ago by tfahle

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.

comment:2 Changed 10 years ago by tfahle

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 onLB: 195.30514 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.421104 row cuts, 12 active, 41 col cuts
probing forceOnStrong LB: 245.235823row cuts, 43 active, 45 col cuts
CBC 2.2.2 probing onLB: 160.2360 row cuts, 0 active, 0 col cuts
probing forceOnStrongLB: 160.236 0 row cuts, 0 active, 0 col cuts
CBC 2.3.0probing on LB: 160.236 0 row cuts, 0 active, 0 col cuts
probing forceOnStrongLB: 160.236 0 row cuts, 0 active, 0 col cuts

all tests under WinXP using Visual Studio 2005 in debug mode

comment:3 Changed 7 weeks ago by stefan

  • Resolution set to migrated
  • Status changed from new to closed

This ticket has been migrated to GitHub and will be resolved there: https://github.com/coin-or/Cbc/issues/78

Note: See TracTickets for help on using tickets.