[Coin-discuss] cbc returns non-integer solution to integer problem
Esben Mose Hansen
esben at sirius.ange.dk
Mon Oct 30 10:41:18 EST 2006
Hi list :)
I hope this is the correct list; it was the closest match I could find on the
webpage.
I seem to have hit a bug in cbc. I have a (pure) integer problem, to which the
cbc solver returns a solution with C000025=0.375. cplex and glpk correctly
returns a proper solution (with a total cost a bit over 1e6.). Solving
without using the preprocessor returns the correct answer (but uses 10x as
much time as glpk). So... is this the correct place for bug reports on
cbcsolve? Or I am missing something obvious?
Attached is the original problem in the mps format, and below is a log of a
session with cbc.
esben at mosegris:~/ange-fs/externals/solver$ cbc prob.mps -
Coin Cbc and Clp Solver version 1.01.00, build Oct 3 2006
command line - cbc prob.mps -
At line 1 NAME BLANK
At line 2 ROWS
At line 251 COLUMNS
At line 1501 RHS
At line 1589 BOUNDS
At line 1867 ENDATA
Problem BLANK has 247 rows, 277 columns and 2101 elements
Model was imported from ./prob.mps in 0.008001 seconds
Switching to line mode
Coin:solve
Optimal - objective value 6237.92
Cgl0003I 0 fixed, 0 tightened bounds, 88 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 88 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 80 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 80 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 80 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 80 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 80 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 80 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 80 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 80 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 80 strengthened rows, 0 substitutions
Cgl0004I processed model has 154 rows, 97 columns (97 integer) and 789
elements
processed model has 154 rows, 97 columns and 789 elements
Optimal - objective value 6237.51
97 integer variables
Cbc0009I Objective coefficients multiple of 1
cutoff increment increased from 1e-05 to 0.999
pass 1: obj. 0.00000 --> up = 1 , down = 0 - solution found
Cbc0012I Integer solution of 505961 found by heuristic after 1 iterations and
0 nodes (0.71 seconds)
Cbc0031I 48 added rows had average density of 18.4792
Cbc0013I At root node, 48 cuts changed objective from 6237.51 to 505902 in 100
passes
Cbc0014I Cut generator 0 (Probing) - 2981 row cuts (26 active), 2 column cuts
in 1.86412 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 2340 row cuts (16 active), 0 column cuts
in 0.244013 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts (0 active), 0 column cuts in
0.004 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Reduce-and-split) - 178 row cuts (0 active), 0
column cuts in 0.320027 seconds - new frequency is -100
Cbc0014I Cut generator 4 (Clique) - 0 row cuts (0 active), 0 column cuts
in -1.75099e-17 seconds - new frequency is -100
Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 64 row cuts (0 active), 0
column cuts in 0.056004 seconds - new frequency is -100
Cbc0014I Cut generator 6 (FlowCover) - 131 row cuts (0 active), 0 column cuts
in 0.14401 seconds - new frequency is -100
Cbc0014I Cut generator 7 (TwoMirCuts) - 600 row cuts (6 active), 0 column cuts
in 0.080004 seconds - new frequency is -100
Cbc0001I Search completed - best objective 505961, took 2887 iterations and 0
nodes (4.46 seconds)
Cbc0032I Strong branching done 82 times (3313 iterations), fathomed 1 nodes
and fixed 18 variables
Cuts at root node changed objective from 6237.51 to 505924
Probing was tried 100 times and created 2981 cuts of which 26 were active
after adding rounds of cuts ( 1.86412 seconds)
Gomory was tried 100 times and created 2340 cuts of which 16 were active after
adding rounds of cuts ( 0.244013 seconds)
Knapsack was tried 100 times and created 0 cuts of which 0 were active after
adding rounds of cuts ( 0.004 seconds)
Reduce-and-split was tried 100 times and created 178 cuts of which 0 were
active after adding rounds of cuts ( 0.320027 seconds)
Clique was tried 1 times and created 0 cuts of which 0 were active after
adding rounds of cuts ( -1.75099e-17 seconds)
MixedIntegerRounding2 was tried 100 times and created 64 cuts of which 0 were
active after adding rounds of cuts ( 0.056004 seconds)
FlowCover was tried 100 times and created 131 cuts of which 0 were active
after adding rounds of cuts ( 0.14401 seconds)
TwoMirCuts was tried 100 times and created 600 cuts of which 6 were active
after adding rounds of cuts ( 0.080004 seconds)
Result - Finished objective 505961 after 0 nodes and 2887 iterations - took
4.7683 seconds
Coin:solu $
24 C0000025 1 -3.652224e-17
25 C0000026 0.375 1.1293305e-16
44 C0000045 5 -2.9817938e-14
49 C0000050 7 1.8264526e-14
50 C0000051 1 5
54 C0000055 7 -2.1385815e-14
55 C0000056 1 -2.0385638e-14
59 C0000060 7 2.9942487e-15
60 C0000061 1 4.9042648e-15
62 C0000063 1 2.9317056e-15
64 C0000065 6 -6.539658e-15
65 C0000066 1 -6.362996e-15
69 C0000070 7 1.1726823e-14
70 C0000071 1 7.4609657e-15
74 C0000075 7 2.0091956e-14
75 C0000076 1 2.2095334e-14
77 C0000078 2 2.0459396e-14
79 C0000080 5 2.0459396e-14
80 C0000081 1 2.0725486e-14
84 C0000085 8 2.0826837e-14
89 C0000090 5 -1.1774703e-14
90 C0000091 2 -2.2198539e-14
94 C0000095 4 -1.1476242e-14
95 C0000096 2 -1.1463318e-14
96 C0000097 2 5.3029306e-15
98 C0000099 2 3.9601639e-15
103 C0000104 3 4.9821728e-15
156 C0000157 5 5.3029306e-15
161 C0000162 3 3.0394972e-15
276 C0000277 5 99820
--
kind regards, Esben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: prob.mps.bz2
Type: application/x-bzip2
Size: 6181 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20061030/0e4ad0d4/attachment.bz2>
More information about the Coin-discuss
mailing list