Wrong result for ILP, regression in the last 1 or 2 months

[christoph-cullmann]

See the attached ILP
value_3810812.lp.gz

I updated my local CBC to current master (including osi,coinutils,...), now cbc computes a different result (mismatching the cplex one)

❯ ../usr/bin/cbc /local/ssd/cullmann/build/lpsolve.clpsolve/lpsolve.clpsolve/test/value_3810812.lp
Welcome to the CBC MILP Solver
Version: trunk
Build Date: Aug 27 2024
command line - /local/ssd/cullmann/build/lpsolve.clpsolve/lpsolve.clpsolve/test/value_3810812.lp (default strategy 1)
 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Problem value_3810812.lp has 323252 rows, 345638 columns and 779275 elements
Coin0009I Switching back to maximization to get correct duals etc
Continuous objective value is 3.81114e+06 - 1.1533 seconds
Cgl0003I 0 fixed, 429 tightened bounds, 24 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 134 tightened bounds, 19 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 16 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 9 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0004I processed model has 632 rows, 5585 columns (5585 integer (3563 of which binary)) and 11494 elements
Coin3009W Conflict graph built in 0.001 seconds, density: 0.050%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cbc0038I Initial state - 78 integers unsatisfied sum - 24.8557
Cbc0038I Solution found of 3.81106e+06
Cbc0038I Branch and bound needed to clear up 78 general integers
Cbc0038I Full problem 632 rows 5585 columns, reduced to 289 rows 1982 columns
Cbc0038I Cleaned solution of 3.8108e+06
Cbc0038I Before mini branch and bound, 5507 integers at bound fixed and 0 continuous of which 167 were internal integer and 0 internal continuous
Cbc0038I Mini branch and bound did not improve solution (3.06 seconds)
Cbc0038I Round again with cutoff of 3.81082e+06
Cbc0038I Reduced cost fixing fixed 309 variables on major pass 2
Cbc0038I Solution found of 3.81106e+06
Cbc0038I Branch and bound needed to clear up 78 general integers
Cbc0038I Full problem 633 rows 5585 columns, reduced to 247 rows 1859 columns
Cbc0038I Mini branch and bound could not fix general integers
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 5507 integers at bound fixed and 0 continuous of which 167 were internal integer and 0 internal continuous
Cbc0038I Mini branch and bound did not improve solution (3.30 seconds)
Cbc0038I After 3.31 seconds - Feasibility pump exiting with objective of 3.8108e+06 - took 0.62 seconds
Cbc0012I Integer solution of 3810796 found by feasibility pump after 0 iterations and 0 nodes (3.31 seconds)
Cbc0038I Full problem 632 rows 5585 columns, reduced to 69 rows 103 columns
Cbc0012I Integer solution of 3810807 found by RINS after 0 iterations and 0 nodes (3.46 seconds)
Cbc0031I 41 added rows had average density of 6.0243902
Cbc0013I At root node, 196 cuts changed objective from 3811056 to 3810811.7 in 9 passes
Cbc0014I Cut generator 0 (Probing) - 8 row cuts average 4.4 elements, 38 column cuts (68 active)  in 0.116 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 133 row cuts average 6.4 elements, 0 column cuts (0 active)  in 0.006 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.002 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 953 row cuts average 2.0 elements, 0 column cuts (0 active)  in 0.011 seconds - new frequency is 1
Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.008 seconds - new frequency is -100
Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.099 seconds - new frequency is -100
Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 7 (TwoMirCuts) - 287 row cuts average 6.7 elements, 0 column cuts (0 active)  in 0.009 seconds - new frequency is -100
Cbc0014I Cut generator 8 (ZeroHalf) - 13 row cuts average 5.8 elements, 0 column cuts (0 active)  in 0.007 seconds - new frequency is -100
Cbc0001I Search completed - best objective 3810807, took 219 iterations and 0 nodes (3.75 seconds)
Cbc0035I Maximum depth 0, 318 variables fixed on reduced cost
Cuts at root node changed objective from 3.81106e+06 to 3.81081e+06
Probing was tried 9 times and created 46 cuts (0.11636 seconds)
Gomory was tried 9 times and created 133 cuts (0.006054 seconds)
Knapsack was tried 9 times and created 0 cuts (0.002253 seconds)
Clique was tried 9 times and created 953 cuts (0.01117 seconds)
OddWheel was tried 9 times and created 0 cuts (0.008488 seconds)
MixedIntegerRounding2 was tried 9 times and created 0 cuts (0.099061 seconds)
FlowCover was tried 9 times and created 0 cuts (0.001188 seconds)
TwoMirCuts was tried 9 times and created 287 cuts (0.008898 seconds)
ZeroHalf was tried 9 times and created 13 cuts (0.006659 seconds)

Result - Optimal solution found
Objective value:                3810807
Enumerated nodes:               0
Total iterations:               219
Time (CPU seconds):             4.29664
Time (Wallclock seconds):       4.66537
Total time (CPU seconds):       4.95365   (Wallclock seconds):       5.37705

[tkralphs]

Could you use git bisect to find the exact commit where the change occurred? That would probably help, although it could be that this is due to a pre-existing bug and some unrelated change caused the solution process to change in a way that tickled the bug.

[christoph-cullmann]

That is not that easy as I use a mirror that just not contains all that stuff and can't use the repos as is as I need it CMake based. If I have more hints where the issue might be, I can add that here.

I have a bunch of ILPs with results 'verified' with a second solver like cplex that I use as regression tests, is there some way to add such stuff to the auto tests?

https://github.com/christoph-cullmann/ilp

At least all x months they find regressions in cbc and Co.

[jjhforrest]

I have many versions of master. The one I am working on most now lacks many recent updates and gets correct answer. A vanilla up to date master does get the answer wrong - so I can slowly find problem. At a first glance it looks like a bad cut generator. If I add -cgraph clq to go back to old type cliques it solves correctly.

As to auto tests. I have a directory ~/cullmann with files and a file testset in that directory and then
cbc -dirmiplib ~/cullmann ..... works (you do need to set a maximum nodes or seconds as cbc does not do too well on a few problems).

[jjhforrest]

Problem is CoinStaticConflictGraph - may take some time to work out what it does/did.

[christoph-cullmann]

Thanks as lot for investigating this!

If it is of any help, the other test that has different results for me with the current version is

https://github.com/christoph-cullmann/ilp/blob/main/value_28841479959.lp

That is now just infeasible:

❯ ../usr/bin/cbc ../lpsolve.clpsolve/test/value_28841479959.lp
Welcome to the CBC MILP Solver
Version: trunk
Build Date: Aug 29 2024
command line - ../lpsolve.clpsolve/test/value_28841479959.lp (default strategy 1)
 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Problem value_28841479959.lp has 8062 rows, 22012 columns and 52444 elements
Coin0009I Switching back to maximization to get correct duals etc
Continuous objective value is 2.88415e+10 - 0.690207 seconds
Cgl0003I 0 fixed, 7536 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 3 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 4610 rows, 16352 columns (16352 integer (917 of which binary)) and 41524 elements
Coin3009W Conflict graph built in 0.003 seconds, density: 0.006%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cbc0031I 20 added rows had average density of 43.7
Cbc0013I At root node, 145 cuts changed objective from 2.884148e+10 to 2.8841372e+10 in 11 passes
Cbc0014I Cut generator 0 (Probing) - 8 row cuts average 2.5 elements, 22 column cuts (22 active)  in 0.353 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 10 row cuts average 387.4 elements, 0 column cuts (0 active)  in 0.019 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.010 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 421 row cuts average 2.0 elements, 0 column cuts (0 active)  in 0.002 seconds - new frequency is 1
Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.002 seconds - new frequency is -100
Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.017 seconds - new frequency is -100
Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.008 seconds - new frequency is -100
Cbc0001I Search completed - best objective -1e+50, took 121 iterations and 0 nodes (1.60 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 2.88415e+10 to 2.88414e+10
Probing was tried 11 times and created 30 cuts (0.353472 seconds)
Gomory was tried 11 times and created 10 cuts (0.018909 seconds)
Knapsack was tried 11 times and created 0 cuts (0.010064 seconds)
Clique was tried 11 times and created 421 cuts (0.002397 seconds)
OddWheel was tried 11 times and created 0 cuts (0.00194 seconds)
MixedIntegerRounding2 was tried 11 times and created 0 cuts (0.016779 seconds)
FlowCover was tried 11 times and created 0 cuts (0.008125 seconds)
TwoMirCuts was tried 1 times and created 0 cuts (0.003247 seconds)
ZeroHalf was tried 1 times and created 0 cuts (0.009432 seconds)

Result - Problem proven infeasible
No feasible solution found
Enumerated nodes:               0
Total iterations:               121
Time (CPU seconds):             1.59816
Time (Wallclock seconds):       1.61948
Total time (CPU seconds):       1.62267   (Wallclock seconds):       1.64403

[jjhforrest]

Many models on standard tests get wrong answer too!

The problem was introduced by using std::vector more. You can get use of uninitialized values in CoinAdjacencyVector (that is easily fixed). However the problem here is using size() as a test for whether a vector is empty in CoinStaticConflictGraph. Maybe someone who know code better than I do could fix - otherwise it will take a bit of time.

[jjhforrest]

Hope I have fixed it in master.

[jhmgoossens]

I think the std::vector changes were part of PR240 on CoinUtils. There may be more surprises there.

[christoph-cullmann]

Thanks, at least my initial regression tests work for all things that did work in the old release I had.

[h-g-s]

I would recommend rolling back the changes to vector. When Samuel was developing the conflict graph infrastructure, we did some benchmarking on code that used it versus code with pointers and arrays and performance degradation with vectors was noticeable.

…

On Fri, Aug 30, 2024, 03:20 John Forrest ***@***.***> wrote: Many models on standard tests get wrong answer too! The problem was introduced by using std::vector more. You can get use of uninitialized values in CoinAdjacencyVector (that is easily fixed). However the problem here is using size() as a test for whether a vector is empty in CoinStaticConflictGraph. Maybe someone who know code better than I do could fix - otherwise it will take a bit of time. — Reply to this email directly, view it on GitHub <#668 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AB4VZOXWWMJI42NSBGHVJ4TZUBBOLAVCNFSM6AAAAABNGFJHJWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGMRQG43DIOJRGU> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>