search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11.34k stars 2.14k forks source link

CBC failure via or-tools but success via command-line #642

Closed mmcloughlin closed 5 years ago

mmcloughlin commented 6 years ago

I have a mixed-integer programming problem such that

My current theory is that CBC is run with different parameters in the two cases. In particular the preprocessing step seems to be enabled via or-tools but not from the command line, and through or-tools I get warnings in the solver output. Unfortunately the CBC interface has very poor support for modifying underlying solver parameters.

I would switch to a different solver but I have strong interest in CBC because of the permissive license.

Any help/ideas appreciated.

More details:

Output from the solver when run from or-tools:

processed model has 256 rows, 1009 columns (1008 integer) and 2020 elements
Pass   1: suminf.    0.00000 (0) obj. 1.64818e+11 iterations 12
Solution found of 1.64818e+11
Before mini branch and bound, 1004 integers at bound fixed and 0 continuous
processed model has 5 rows, 5 columns (4 integer) and 12 elements
Full problem 256 rows 1009 columns, reduced to 5 rows 5 columns
At root node, 0 cuts changed objective from 1.4447084e+11 to 1.4447084e+11 in 1 passes
Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 1 column cuts (1 active)
Integer solution of 1.4447084e+11 found by strong branching after 1 iterations and 0 nodes (2.50 seconds)
Search completed - best objective 144470841812, took 1 iterations and 0 nodes (2.50 seconds)
Strong branching done 4 times (10 iterations), fathomed 1 nodes and fixed 0 variables
Maximum depth 0, 0 variables fixed on reduced cost
Mini branch and bound improved solution from 1.64818e+11 to 1.44471e+11 (0.01 seconds)
Round again with cutoff of 1.44471e+11
Pass   2: suminf.    0.55134 (2) obj. 1.44471e+11 iterations 1
Pass   3: suminf.    0.00000 (0) obj. 1.44471e+11 iterations 4
Solution found of 1.44471e+11
Before mini branch and bound, 1004 integers at bound fixed and 0 continuous
Mini branch and bound did not improve solution (0.01 seconds)
After 0.01 seconds - Feasibility pump exiting with objective of 1.44471e+11 - took 0.00 seconds
Integer solution of 1.4447084e+11 found by feasibility pump after 0 iterations and 0 nodes (0.01 seconds)
Search completed - best objective 144470841812, took 0 iterations and 0 nodes (0.01 seconds)
Maximum depth 0, 0 variables fixed on reduced cost

Then from VerifySolution() I get

WARNING: Logging before InitGoogleLogging() is written to STDERR
E0403 21:50:16.124837 10031 linear_solver.cc:1164] Activity -3.05176e-05 too low for Constraint '<...>': <linear expr> ≥ 0.000000
E0403 21:50:16.125062 10031 linear_solver.cc:1219] There were 1 errors above the tolerance (1e-07), the largest was 3.05176e-05

After exporting the problem and running cbc on the command line I see

$ cbc /tmp/problem.mps 
Welcome to the CBC MILP Solver 
Version: 2.8.7 
Build Date: Dec 28 2013 

command line - cbc /tmp/problem.mps (default strategy 1)
At line 9 NAME          optimize_balance
At line 10 ROWS
At line 354 COLUMNS
At line 1964 RHS
At line 2136 BOUNDS
At line 3490 ENDATA
Problem optimize_balance has 342 rows, 1353 columns and 2364 elements
Coin0008I optimize_balance read with 0 errors
Continuous objective value is -2.58384e+11 - 0.00 seconds
Cgl0004I processed model has 256 rows, 1009 columns (1008 integer) and 2020 elements
Cbc0038I Pass   1: suminf.    0.00000 (0) obj. -2.38037e+11 iterations 12
Cbc0038I Solution found of -2.38037e+11
Cbc0038I Before mini branch and bound, 1004 integers at bound fixed and 0 continuous
Cbc0038I Full problem 256 rows 1009 columns, reduced to 5 rows 5 columns
Cbc0038I Mini branch and bound improved solution from -2.38037e+11 to -2.58384e+11 (0.01 seconds)
Cbc0038I Round again with cutoff of -2.58384e+11
Cbc0038I Pass   2: suminf.    0.55134 (2) obj. -2.58384e+11 iterations 1
Cbc0038I Pass   3: suminf.    0.00000 (0) obj. -2.58384e+11 iterations 4
Cbc0038I Solution found of -2.58384e+11
Cbc0038I Before mini branch and bound, 1004 integers at bound fixed and 0 continuous
Cbc0038I Mini branch and bound did not improve solution (0.01 seconds)
Cbc0038I After 0.01 seconds - Feasibility pump exiting with objective of -2.58384e+11 - took 0.01 seconds
Cbc0012I Integer solution of -2.5838413e+11 found by feasibility pump after 0 iterations and 0 nodes (0.01 seconds)
Cbc0001I Search completed - best objective -258384125648.5, took 0 iterations and 0 nodes (0.01 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
0  Obj -2.5838413e+11 Primal inf 10142.314 (4) Dual inf 1.3405678e+09 (3)
Perturbing problem by 0.001 %% of 5562.1007 - largest nonzero change 0 (%% 0) - largest zero change 0
3  Obj -2.5838413e+11
Optimal - objective value -2.5838413e+11
Cuts at root node changed objective from -2.58384e+11 to -2.58384e+11
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                -258384125648.50000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.02
Time (Wallclock seconds):       0.03

Total time (CPU seconds):       0.02   (Wallclock seconds):       0.03
mmcloughlin commented 6 years ago

I have transitioned to using CBC directly, together with a hand-rolled wrapper layer akin to or-tools cbc_interface.cc.

I have been able to resolve my issue by adding -preprocess off to the arguments to callCbc. In or-tools this appears here

https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/cbc_interface.cc#L365

Clearly this is not a good option universally, since anecdotally it worsens performance slightly (as you would expect). However I wonder if these arguments could be exposed via the SetSolverSpecificParametersAsString mechanism?

https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/linear_solver.h#L460

I'm assuming this comment is the reason why that's not a good idea

https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/cbc_interface.cc#L466-L470

Do you have any context on this, and how hard it would be to patch CBC itself?

lperron commented 6 years ago

There is a Presolve parameter on the linear solver. You should use it.

Now this is clearly a CBC bug, you can send the MPS file to the cbc owners. I would not try to fix it myself.

Thanks Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le ven. 6 avr. 2018 à 04:55, Michael McLoughlin notifications@github.com a écrit :

I have transitioned to using CBC directly, together with a hand-rolled wrapper layer akin to or-tools cbc_interface.cc https://github.com/google/or-tools/blob/v6.6/ortools/linear_solver/cbc_interface.cc .

I have been able to resolve my issue by adding -preprocess off to the arguments to callCbc. In or-tools this appears here

https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/cbc_interface.cc#L365

Clearly this is not a good option universally, since anecdotally it worsens performance slightly (as you would expect). However I wonder if these arguments could be exposed via the SetSolverSpecificParametersAsString mechanism?

https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/linear_solver.h#L460

I'm assuming this comment is the reason why that's not a good idea

https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/cbc_interface.cc#L466-L470

Do you have any context on this, and how hard it would be to patch CBC itself?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/642#issuecomment-379134540, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17cQ7cHBsG0wC3r5nJR2Akk_aGxWhks5tltkQgaJpZM4TGLLk .

mmcloughlin commented 6 years ago

There is a Presolve parameter on the linear solver. You should use it.

It's ignored by the CBC interface.

https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/cbc_interface.cc#L358-L360 https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/cbc_interface.cc#L497-L505

Now this is clearly a CBC bug, you can send the MPS file to the cbc owners. I would not try to fix it myself.

I am increasingly unimpressed by CBC to be honest. I now have a problem where it's selecting the value 2 for a binary variable.

lperron commented 6 years ago

We do not use CBC ourselves. I find it unreliable. I have not yet tried SCIP 5.0 yet. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le ven. 6 avr. 2018 à 20:06, Michael McLoughlin notifications@github.com a écrit :

There is a Presolve parameter on the linear solver. You should use it.

It's ignored by the CBC interface.

https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/cbc_interface.cc#L358-L360

https://github.com/google/or-tools/blob/e993c93f4afbb6d772354fca2cd8e6bfe511cf8e/ortools/linear_solver/cbc_interface.cc#L497-L505

Now this is clearly a CBC bug, you can send the MPS file to the cbc owners. I would not try to fix it myself.

I am increasingly unimpressed by CBC to be honest. I now have a problem where it's selecting the value 2 for a binary variable.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/642#issuecomment-379332066, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17Tl5FarJJuwlMYndbCyQpkXzeZ0hks5tl66jgaJpZM4TGLLk .

yingzong commented 6 years ago

I've been working on this: #638, and also would like some context on that comment about the memory leak.

jlo1 commented 6 years ago

@lperron curious, which do you recommend for Mixed Integer Programming? From here, seems like CBC is the default?

mmcloughlin commented 6 years ago

@jlo1 I can't speak for the authors, but I would guess CBC is the default only because of its permissive license. All of the others need some kind of license that ortools developers cannot be sure people will have.

As for a recommendation, it will depend on your use case and which licenses you can acquire. But open source benchmarks suggest the following performance ranking (best to worst):

  1. Gurobi
  2. SCIP
  3. CBC
  4. GLPK
Mizux commented 6 years ago

Guroby is proprietary, need a license key SCIP they require you to download it form their web site i.e. we can't integrate it in or-tools (also dual license academic/commercial so you must register etc....) GLPK worse than CBC -> or-tools shipped with CBC by default so binary package will(could) only contain it.