[Cbc] Non integer result in an ILP
Rafael Lopez
Rafael.Lopez at lri.fr
Thu Dec 6 04:18:01 EST 2007
Hi,
I've been preparing simple exercises for my students to make them use
cplex and cbc, and I've stumbled upon some odd Cbc behavior:
when asking him to solve a fairly simple (M)IP, Cbc consistently returns
one fractional variable (99.5) when I know there are optimal integer
solutions. I'm a bit surprised it is even possible, although I think I
have an idea of why it happens.
I apologize for the length of this mail.
The mps file of the problem is:
NAME myproblem
ROWS
N opt
L c1
L c2
L c3
L c4
L c5
L c6
E c7
L c8
L c9
L c10
G c11
L c12
L c13
E c14
COLUMNS
MARK0000 'MARKER' 'INTORG'
s opt -1 c1 1
s c5 2 c8 160
s c10 0.05 c11 0.1
s c14 1
f opt -1 c1 1
f c5 3 c8 240
f c9 30 c10 0.05
f c11 0.1 c14 1
ch opt -1 c1 1
ch c5 4 c8 290
ch c9 60 c10 0.05
ch c11 0.1 c14 1
pr opt -1 c2 1
pr c5 2 c8 160
pr c9 60 c10 -0.95
pr c11 -0.9 c14 1
so opt -1 c2 1
so c5 2 c8 180
so c10 0.05 c11 0.1
so c14 1
gy opt -1 c3 1
gy c5 2 c8 220
gy c9 60 c10 0.05
gy c11 0.1 c12 -1
gy c13 1 c14 1
mo opt -1 c3 1
mo c5 3 c8 210
mo c9 70 c10 0.05
mo c11 0.1 c14 1
ta opt -1 c3 1
ta c5 4 c8 230
ta c9 60 c10 0.05
ta c11 0.1 c14 1
gry opt -1 c4 1
gry c5 4 c8 330
gry c9 70 c10 0.05
gry c11 0.1 c12 -1
gry c13 1 c14 1
ca c1 -40 c6 1
ca c8 240 c9 80
sa c2 -20 c6 1
sa c8 210 c9 90
at c3 -25 c6 2
at c8 240 c9 50
vo c4 -10 c6 2
vo c8 250 c9 120
p c5 1 c6 -1
p c8 90
food c5 -1 c7 -1
fe c7 6 c8 80
fe c9 20
or c8 -1
bois c9 -1
total c12 0.2 c13 -0.4
total c14 -1
MARK0001 'MARKER' 'INTEND'
RHS
BOUNDS
LI bnd s 0
LI bnd f 0
LI bnd ch 0
LI bnd pr 0
LI bnd so 0
LI bnd gy 0
LI bnd mo 0
LI bnd ta 0
LI bnd gry 0
UP bnd ca 3
UP bnd sa 3
UP bnd at 3
UP bnd vo 3
UP bnd p 15
LI bnd food 0
LI bnd fe 0
LI bnd or 0
LI bnd bois 0
LI bnd total 0
ENDATA
Here's the log (same results in 1.1):
./cbc
Coin Cbc and Clp Solver version 2.00.00, build Nov 26 2007
CoinSolver takes input from arguments ( - switches to stdin)
Enter ? for list of commands or help
Coin:import myproblem.mps
At line 1 NAME myproblem
At line 2 ROWS
At line 18 COLUMNS
At line 76 RHS
At line 77 BOUNDS
At line 97 ENDATA
Problem myproblem has 14 rows, 19 columns and 94 elements
Coin0008I myproblem read with 0 errors
Coin:solve
Continuous objective value is -270 - 0.00 seconds
Cgl0003I 0 fixed, 4 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 9 rows, 10 columns (10 integer) and 38
elements Objective coefficients multiple of 1
Cutoff increment increased from 1e-05 to 0.999
Cbc0012I Integer solution of -265 found by rounding after 3 iterations and
0 nodes (0.00 seconds)
Cbc0031I 2 added rows had average density of 7
Cbc0013I At root node, 2 cuts changed objective from -270 to -265 in 3
passes Cbc0014I Cut generator 0 (Probing) - 0 row cuts (0 active), 0
column cuts in 0.000 seconds - new frequency is 10
Cbc0014I Cut generator 1 (Gomory) - 5 row cuts (1 active), 0 column cuts
in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts (0 active), 0 column cuts
in 0.000 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.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts (0 active), 0 column
cuts in -0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 6 row cuts (1 active), 0 column
cuts in 0.000 seconds - new frequency is -100
Cbc0001I Search completed - best objective -265, took 3 iterations and 0
nodes (0.00 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from -270 to -265
Probing was tried 3 times and created 0 cuts of which 0 were active after
adding rounds of cuts (0.000 seconds)
Gomory was tried 3 times and created 5 cuts of which 1 were active after
adding rounds of cuts (0.000 seconds)
Knapsack was tried 3 times and created 0 cuts of which 0 were active after
adding rounds of cuts (0.000 seconds)
Clique was tried 3 times and created 0 cuts of which 0 were active after
adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 1 times and created 0 cuts of which 0 were
active after adding rounds of cuts (-0.000 seconds)
FlowCover was tried 1 times and created 0 cuts of which 0 were active
after adding rounds of cuts (-0.000 seconds)
TwoMirCuts was tried 3 times and created 6 cuts of which 1 were active
after adding rounds of cuts (0.000 seconds)
Result - Finished objective -265 after 0 nodes and 3 iterations - took
0.01 seconds (total time 0.02)
Coin:solution solution.txt
Coin:quit
Total time 0.02
And the solution file:
cat solution.txt
0 s 120 3.5026968e-17
1 f 0 3.5026968e-17
2 ch 0 3.5019906e-17
3 pr 14 1.7601345e-17
4 so 46 1.7541731e-17
5 gy 43 -5.1062163e-17
6 mo 32 -5.0971204e-17
7 ta 0 -5.100096e-17
8 gry 10 -5.2434523e-17
9 ca 3 -35
10 sa 3 -15
11 at 3 -15
12 vo 1 2.5240227e-16
13 p 15 -5
14 food 597 0
15 fe 99.5 0
16 or 60830 0
17 bois 9130 0
18 total 265 0
Note the fe = 99.5.
I also know that a solution to that problem exist with all integers:
CPLEX> d so va -
Variable Name Solution Value
s 120.000000
pr 26.000000
so 34.000000
gy 75.000000
gry 10.000000
ca 3.000000
sa 3.000000
at 3.000000
vo 1.000000
p 14.000000
food 564.000000
fe 94.000000
or 60381.000000
bois 9420.000000
total 265.000000
All other variables in the range 1-19 are zero.
I know there are multiple optimal solutions, but I would expect cbc to
give me one that at least doesn't have a variable that fails to be an
integer.
I think what happens is that Cbc gets the variables in the objective
function "integered" first, then sets some others, and for leftover
variables forgets about the constraint of them being integer aswell.
Just my impression on it, really, since putting "fe" in the objective
with a very small coefficient leads to that variable to indeed be
integer at the end.
Cordially,
R. Lopez
More information about the Cbc
mailing list