[Coin-discuss] cbc returns non-integer solution to integer problem
John J Forrest
jjforre at us.ibm.com
Mon Oct 30 12:42:42 EST 2006
Esben,
Error does not seem to exist on branches/devel but does on trunk (and
presumably on stable).
Will try and find time to look at it.
John Forrest
Esben Mose Hansen <esben at ange.dk>
Sent by: coin-discuss-bounces at list.coin-or.org
10/30/2006 10:44 AM
Please respond to
Discussions about open source software for Operations Research
<coin-discuss at list.coin-or.org>
To
coin-discuss at list.coin-or.org
cc
Subject
[Coin-discuss] cbc returns non-integer solution to integer problem
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
[attachment "prob.mps.bz2" deleted by John J Forrest/Watson/IBM]
_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20061030/a32b09f4/attachment.html>
More information about the Coin-discuss
mailing list