search

coin-or / Cgl

Cut Generator Library
Other
24 stars 16 forks source link

Large preprocessing difference between clang/Linux or macOS 64-bit CBC and MSVC #57

Open christoph-cullmann opened 3 years ago

christoph-cullmann commented 3 years ago

See the attached ILP.

value_87454.lp.gz

With a Linux 64-bit build of the standalone CBC solver (master branch of all coin-or repos, uses only CoinUtils/Clp/Cgl/Cbc, no other extra solver deps), this solves nicely with e.g.

cbc value_87454.lp -gomory=forceLongOn -solve

 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Coin0009I Switching back to maximization to get correct duals etc
Option for gomoryCuts changed from ifmove to forceLongOn
Continuous objective value is 87887 - 0.04 seconds
Cgl0003I 24 fixed, 0 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0003I 6 fixed, 18 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
Cgl0003I 3 fixed, 8 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 491 rows, 2455 columns (2455 integer (288 of which binary)) and 7404 elements
Coin3009W Conflict graph built in 0.001 seconds, density: 0.030%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cutoff increment increased from 0.0001 to 0.9999
Cbc0012I Integer solution of -86044 found by DiveCoefficient after 316 iterations and 0 nodes (0.81 seconds)
Cbc0031I 7 added rows had average density of 265.85714
Cbc0013I At root node, 7 cuts changed objective from -87887 to -87887 in 10 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.048 seconds - new frequency is -100
Cbc0014I Cut generator 1 (Gomory) - 166 row cuts average 713.9 elements, 0 column cuts (0 active)  in 0.173 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.009 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.010 seconds - new frequency is -100
Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.027 seconds - new frequency is -100
Cbc0014I Cut generator 7 (TwoMirCuts) - 164 row cuts average 190.4 elements, 0 column cuts (0 active)  in 0.039 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, -86044 best solution, best possible -87887 (0.85 seconds)
Cbc0038I Full problem 491 rows 2455 columns, reduced to 29 rows 28 columns
Cbc0012I Integer solution of -86502 found by RINS after 380 iterations and 1 nodes (0.93 seconds)
Cbc0012I Integer solution of -86920 found by DiveCoefficient after 456 iterations and 3 nodes (1.06 seconds)
Cbc0010I After 12 nodes, 11 on tree, -86920 best solution, best possible -87887 (1.55 seconds)
Cbc0010I After 37 nodes, 25 on tree, -86920 best solution, best possible -87887 (2.26 seconds)
Cbc0038I Full problem 491 rows 2455 columns, reduced to 54 rows 71 columns
Cbc0012I Integer solution of -87428 found by RINS after 1859 iterations and 41 nodes (2.39 seconds)
Cbc0004I Integer solution of -87454 found after 1898 iterations and 48 nodes (2.50 seconds)
Cbc0001I Search completed - best objective -87454, took 2113 iterations and 55 nodes (2.74 seconds)
Cbc0032I Strong branching done 1036 times (13721 iterations), fathomed 0 nodes and fixed 0 variables
Cbc0035I Maximum depth 24, 75 variables fixed on reduced cost
Cuts at root node changed objective from -87887 to -87887
Probing was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.048 seconds)
Gomory was tried 72 times and created 655 cuts of which 0 were active after adding rounds of cuts (0.607 seconds)
Knapsack was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.009 seconds)
Clique was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
OddWheel was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
MixedIntegerRounding2 was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.010 seconds)
FlowCover was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.027 seconds)
TwoMirCuts was tried 10 times and created 164 cuts of which 0 were active after adding rounds of cuts (0.039 seconds)
ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.002 seconds)

Result - Optimal solution found

Objective value:                87454.00000000
Enumerated nodes:               55
Total iterations:               2113
Time (CPU seconds):             2.76
Time (Wallclock seconds):       2.88

Total time (CPU seconds):       2.78   (Wallclock seconds):       2.92

If one passes the same to a Windows MSVC 64-bit build you get stuck:

 CoinLpIO::readLp(): Maximization problem reformulated as minimization
Coin0009I Switching back to maximization to get correct duals etc
Option for gomoryCuts changed from ifmove to forceLongOn
Continuous objective value is 87887 - 0.03 seconds
Cgl0003I 24 fixed, 0 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0003I 6 fixed, 18 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
Cgl0003I 3 fixed, 8 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 476 rows, 2444 columns (2444 integer (289 of which binary)) and 7519 elements
Coin3009W Conflict graph built in 0.001 seconds, density: 0.028%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cutoff increment increased from 0.0001 to 0.9999
Cbc0012I Integer solution of -84618 found by DiveCoefficient after 0 iterations and 0 nodes (0.30 seconds)
Cbc0038I Full problem 476 rows 2444 columns, reduced to 9 rows 8 columns
Cbc0031I 4 added rows had average density of 393
Cbc0013I At root node, 4 cuts changed objective from -87887 to -87887 in 10 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 1 column cuts (1 active)  in 0.036 seconds - new frequency is -100
Cbc0014I Cut generator 1 (Gomory) - 138 row cuts average 863.6 elements, 0 column cuts (0 active)  in 0.096 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.014 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
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) - 1 row cuts average 39.0 elements, 0 column cuts (0 active)  in 0.004 seconds - new frequency is -100
Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.019 seconds - new frequency is -100
Cbc0014I Cut generator 7 (TwoMirCuts) - 142 row cuts average 277.3 elements, 0 column cuts (0 active)  in 0.029 seconds - new frequency is -100
Cbc0010I After 1 nodes, 2 on tree, -84618 best solution, best possible -87887 (0.66 seconds)
Cbc0012I Integer solution of -86738 found by DiveCoefficient after 133 iterations and 2 nodes (0.69 seconds)
Cbc0012I Integer solution of -86788 found by DiveCoefficient after 261 iterations and 6 nodes (0.98 seconds)
Cbc0012I Integer solution of -87128 found by DiveCoefficient after 290 iterations and 6 nodes (1.03 seconds)
Cbc0010I After 14 nodes, 12 on tree, -87128 best solution, best possible -87887 (1.36 seconds)
Cbc0004I Integer solution of -87454 found after 632 iterations and 19 nodes (1.47 seconds)
Cbc0010I After 37 nodes, 14 on tree, -87454 best solution, best possible -87887 (2.08 seconds)
Cbc0038I Full problem 476 rows 2444 columns, reduced to 61 rows 87 columns
Cbc0010I After 71 nodes, 32 on tree, -87454 best solution, best possible -87887 (2.78 seconds)
Cbc0038I Full problem 476 rows 2444 columns, reduced to 52 rows 73 columns
............

The interesting diff is the presolving, that already behaves differently and then leads to the following issues.

On Linux/macOS you get

Cgl0004I processed model has 491 rows, 2455 columns (2455 integer (288 of which binary)) and 7404 elements

vs. on Windows

Cgl0004I processed model has 476 rows, 2444 columns (2444 integer (289 of which binary)) and 7519 elements

I am somehow unable to understand how the CglPreprocessing step can end up with such different results. I played with the -preprocess option, but all I tried did end up with differences between the operating systems.

Perhaps this is no bug but just a misuse on my side, any pointers appreciated.

Feel free to use the provided LP as regression test, if needed.

christoph-cullmann commented 3 years ago

I debugged a bit more.

It seems that some of the difference stems from the random numbers generated in coin_init_random_vec().