[Cbc-tickets] Re: [COIN-OR Branch-and-Cut MIP Solver] #36:
CbcSolve.exe (windows) stable release 1.2 returns wrong optimum
COIN-OR Branch-and-Cut MIP Solver
coin-trac at coin-or.org
Sat Nov 17 09:55:58 EST 2007
#36: CbcSolve.exe (windows) stable release 1.2 returns wrong optimum
-------------------------+--------------------------------------------------
Reporter: mserg | Owner: somebody
Type: defect | Status: new
Priority: major | Milestone:
Component: component1 | Version:
Resolution: | Keywords:
-------------------------+--------------------------------------------------
Comment (by jpfasano):
For me Cbc code from trunk built with the MS V8 compiler gets what I think
is the desired answer of 25562.
{{{
D:\COIN\Coin-Cbc-
All\trunk\Cbc\MSVisualStudio\v8\cbcSolve\Release>cbcSolve.exe Shipping.mps
Coin Cbc and Clp Solver version 2.00.00, build Nov 17 2007
command line - cbcSolve.exe Shipping.mps
At line 1 NAME Shipping
At line 2 ROWS
At line 1899 COLUMNS
At line 5716 RHS
At line 5819 BOUNDS
At line 7593 ENDATA
Problem Shipping has 1895 rows, 1773 columns and 7172 elements
Coin0008I Shipping read with 0 errors
Continuous objective value is 18749 - 0.19 seconds
Cgl0006I 16 SOS (1347 members out of 1773) with 0 overlaps - too much
overlap or too many others
Cgl0003I 126 fixed, 0 tightened bounds, 0 strengthened rows, 0
substitutions
Cgl0003I 76 fixed, 0 tightened bounds, 0 strengthened rows, 0
substitutions
Cgl0003I 39 fixed, 0 tightened bounds, 0 strengthened rows, 0
substitutions
Cgl0003I 17 fixed, 0 tightened bounds, 0 strengthened rows, 0
substitutions
Cgl0003I 8 fixed, 0 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0003I 2 fixed, 0 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 1402 rows, 1292 columns (1292 integer) and
5812 elements
Objective coefficients multiple of 1
Cutoff increment increased from 1e-005 to 0.999
Cbc0038I Pass 1: obj. 13.56594 --> up = 0 , down = 0 -- rand =
22 ( 22)
Cbc0038I Pass 2: obj. 16.48135 --> up = 1 , down = 11
Cbc0038I Pass 3: obj. 5.31534 --> up = 0 , down = 0 -- rand =
19 ( 19)
Cbc0038I Pass 4: obj. 9.16744 --> up = 0 , down = 9
Cbc0038I Pass 5: obj. 1.83032 --> up = 0 , down = 1
Cbc0038I Pass 6: obj. 1.56716 --> up = 0 , down = 0 -- rand =
7 ( 13)
Cbc0038I Pass 7: obj. 4.35821 --> up = 0 , down = 5
Cbc0038I Pass 8: obj. 1.35821 --> up = 0 , down = 0 -- rand =
7 ( 22)
Cbc0038I Pass 9: obj. 4.56716 --> up = 0 , down = 5
perturbation applied
Cbc0038I Pass 10: obj. 146.00000 --> up = 1 , down = 145
Cbc0038I Pass 11: obj. 1.92105 --> up = 1 , down = 0
Cbc0038I Pass 12: obj. 0.92105 --> up = 0 , down = 0 -- rand =
3 ( 22)
Cbc0038I Pass 13: obj. 1.85714 --> up = 0 , down = 1
Cbc0038I Pass 14: obj. 1.47253 --> up = 0 , down = 1
Cbc0038I Pass 15: obj. 1.00000 --> up = 0 , down = 0 -- rand =
4 ( 19)
Cbc0038I Pass 16: obj. 3.00000 --> up = 0 , down = 4
perturbation applied
Cbc0038I Pass 17: obj. 145.00000 --> up = 0 , down = 146
Cbc0038I Pass 18: obj. 1.00000 --> up = 0 , down = 0 -- rand =
6 ( 21)
Cbc0038I Pass 19: obj. 5.00000 --> up = 0 , down = 6
perturbation applied
Cbc0038I Pass 20: obj. 156.17910 --> No solution found this major pass
Cbc0038I Before mini branch and bound, 992 integers at bound fixed and 0
continuous
Cbc0038I Full problem 1402 rows 1292 columns, reduced to 234 rows 221
columns
Cbc0038I Mini branch and bound improved solution from 1.79769e+308 to
55724 (1.64 seconds)
Cbc0038I Round again with cutoff of 52078.1
Cbc0038I Pass 20: obj. 13.56594 --> up = 0 , down = 0 -- rand =
26 ( 26)
Cbc0038I Pass 21: obj. 19.75904 --> up = 0 , down = 16
Cbc0038I Pass 22: obj. 8.87782 --> up = 0 , down = 1
Cbc0038I Pass 23: obj. 7.87782 --> up = 0 , down = 0 -- rand =
19 ( 19)
Cbc0038I Pass 24: obj. 11.86546 --> up = 0 , down = 11
Cbc0038I Pass 25: obj. 4.07904 --> up = 0 , down = 0 -- rand =
11 ( 11)
Cbc0038I Pass 26: obj. 5.70769 --> up = 1 , down = 3
Cbc0038I Pass 27: obj. 2.70563 --> up = 0 , down = 0 -- rand =
24 ( 26)
Cbc0038I Pass 28: obj. 5.41228 --> up = 1 , down = 4
Cbc0038I Pass 29: obj. 1.16019 --> up = 0 , down = 0 -- rand =
10 ( 16)
Cbc0038I Pass 30: obj. 6.97137 --> up = 2 , down = 4
Cbc0038I Pass 31: obj. 1.90656 --> up = 0 , down = 0 -- rand =
8 ( 28)
Cbc0038I Pass 32: obj. 4.16831 --> up = 2 , down = 2
perturbation applied
Cbc0038I Pass 33: obj. 165.45297 --> up = 4 , down = 162
Cbc0038I Pass 34: obj. 4.52649 --> up = 3 , down = 0
Cbc0038I Pass 35: obj. 1.82442 --> up = 0 , down = 0 -- rand =
16 ( 26)
Cbc0038I Pass 36: obj. 6.36312 --> up = 0 , down = 6
Cbc0038I Pass 37: obj. 0.93823 --> up = 0 , down = 0 -- rand =
4 ( 18)
Cbc0038I Pass 38: obj. 0.66667 --> up = 0 , down = 0 -- rand =
2 ( 21)
Cbc0038I Pass 39: obj. 1.19444 --> No solution found this major pass
Cbc0038I Before mini branch and bound, 697 integers at bound fixed and 0
continuous
Cbc0038I Full problem 1402 rows 1292 columns, reduced to 546 rows 499
columns
Cbc0038I Mini branch and bound improved solution from 55724 to 32633 (4.85
seconds)
Cbc0038I After 4.85 seconds - Feasibility pump exiting - took 4.84 seconds
Cbc0012I Integer solution of 32633 found by feasibility pump after 0
iterations and 0 nodes (4.85 seconds)
Cbc0031I 37 added rows had average density of 19.3243
Cbc0013I At root node, 37 cuts changed objective from 19264.6 to 22451.6
in 19 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts (0 active), 0 column cuts
in 0.070 seconds - new frequency is 10
Cbc0014I Cut generator 1 (Gomory) - 320 row cuts (17 active), 0 column
cuts in 0.301 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 38 row cuts (6 active), 0 column
cuts in 0.090 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts (0 active), 0 column cuts
in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts (0 active),
0 column cuts in 0.110 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts (0 active), 0 column
cuts in 0.010 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 247 row cuts (12 active), 0 column
cuts in 0.141 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, 32633 best solution, best possible
22451.6 (6.31 seconds)
Cbc0016I Integer solution of 31436 found by strong branching after 4132
iterations and 41 nodes (21.72 seconds)
Cbc3008W Strong branching is fixing too many variables, too expensively!
Cbc0012I Integer solution of 30315 found by rounding after 5863 iterations
and 60 nodes (28.14 seconds)
Cbc0038I Full problem 1402 rows 1292 columns, reduced to 30 rows 29
columns
Cbc0012I Integer solution of 29407 found by rounding after 6807 iterations
and 73 nodes (30.90 seconds)
Cbc0038I Full problem 1402 rows 1292 columns, reduced to 44 rows 45
columns
Cbc0012I Integer solution of 27961 found by combine solutions after 6820
iterations and 74 nodes (31.17 seconds)
Cbc0004I Integer solution of 27891 found after 8194 iterations and 99
nodes (36.97 seconds)
Cbc0038I Full problem 1402 rows 1292 columns, reduced to 50 rows 51
columns
Cbc0004I Integer solution of 27797 found after 13270 iterations and 144
nodes (44.06 seconds)
Cbc0038I Full problem 1402 rows 1292 columns, reduced to 51 rows 53
columns
Cbc0004I Integer solution of 25798 found after 15698 iterations and 180
nodes (53.65 seconds)
Cbc0038I Full problem 1402 rows 1292 columns, reduced to 59 rows 63
columns
Cbc0012I Integer solution of 25695 found by combine solutions after 15703
iterations and 181 nodes (53.99 seconds)
Cbc0016I Integer solution of 25615 found by strong branching after 18852
iterations and 239 nodes (66.16 seconds)
Cbc0038I Full problem 1402 rows 1292 columns, reduced to 63 rows 66
columns
Cbc0012I Integer solution of 25601 found by combine solutions after 18852
iterations and 239 nodes (66.76 seconds)
Cbc0016I Integer solution of 25562 found by strong branching after 23582
iterations and 338 nodes (80.97 seconds)
Cbc0038I Full problem 1402 rows 1292 columns, reduced to 67 rows 70
columns
Cbc0001I Search completed - best objective 25562, took 26730 iterations
and 455 nodes (87.95 seconds)
Cbc0032I Strong branching done 4228 times (153407 iterations), fathomed 33
nodes and fixed 531 variables
Cbc0035I Maximum depth 44, 7893 variables fixed on reduced cost
Cuts at root node changed objective from 19264.6 to 22451.6
Probing was tried 53 times and created 137 cuts of which 34 were active
after adding rounds of cuts (0.180 seconds)
Gomory was tried 350 times and created 870 cuts of which 127 were active
after adding rounds of cuts (1.944 seconds)
Knapsack was tried 19 times and created 38 cuts of which 6 were active
after adding rounds of cuts (0.090 seconds)
Clique was tried 19 times and created 0 cuts of which 0 were active after
adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 19 times and created 0 cuts of which 0
were active after adding rounds of cuts (0.110 seconds)
FlowCover was tried 19 times and created 0 cuts of which 0 were active
after adding rounds of cuts (0.010 seconds)
TwoMirCuts was tried 19 times and created 247 cuts of which 12 were active
after adding rounds of cuts (0.141 seconds)
Result - Finished objective 25562 after 455 nodes and 26730 iterations -
took 89.75 seconds (total time 90.09)
Total time 90.13
}}}
Can you use the code from trunk?
I don't know when there will be a new stable release.
--
Ticket URL: <https://projects.coin-or.org/Cbc/ticket/36#comment:4>
COIN-OR Branch-and-Cut MIP Solver <http://projects.coin-or.org/Cbc>
An LP-based branch-and-cut MIP solver.
More information about the Cbc-tickets
mailing list