[Cbc] CBC reports infeasible, GLPK solves

[Joshua Arnott]

Hello,

I've come across a MILP which CBC reports as proven infeasible, but which
GLPK solves.

I've uploaded the problem in *.lp format here:
http://pastebin.com/EEifbfpy

The problem was automatically generated based on some data. It's one of
many, and is the only one I've come across so far that exhibits this
problem. I guess it's something to do with tolerances or precision in CBC.
Is there anything I can do to get CBC to solve it?

See below the outputs fro CBC and GLPK (via GLPSOL).

Kind regards,

Josh



The output from CBC:

Welcome to the CBC MILP Solver
Version: 2.7.5
Build Date: Nov 10 2011
Revision Number: 1759

command line - C:\MinGW32-xy\msys\1.0\local\bin\cbc.exe -import problem.lp
-gomory on -branchAndCut (default strategy 1)
Coin0009I  CoinLpIO::readLp(): Maximization problem reformulated as
minimization
Option for gomoryCuts changed from ifmove to on
Continuous objective value is -4.72248e+006 - 0.00 seconds
Cgl0003I 0 fixed, 0 tightened bounds, 0 strengthened rows, 23 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 0 strengthened rows, 23 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 0 strengthened rows, 23 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 0 strengthened rows, 23 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 0 strengthened rows, 23 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 0 strengthened rows, 23 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 0 strengthened rows, 23 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 0 strengthened rows, 23 substitutions
Cgl0004I processed model has 23 rows, 46 columns (23 integer) and 46
elements
Cbc0038I Solution found of -4.72139e+006
Cbc0038I Before mini branch and bound, 23 integers at bound fixed and 23
continuous
Cbc0038I Mini branch and bound did not improve solution (0.01 seconds)
Cbc0038I After 0.01 seconds - Feasibility pump exiting with objective of
-4.72139e+006 - took 0.00 seconds
Cbc0012I Integer solution of -4721393.5 found by feasibility pump after 0
iterations and 0 nodes (0.01 seconds)
Cbc0009I Objective coefficients multiple of 0.075
Cbc0001I Search completed - best objective -4721393.495, took 0 iterations
and 0 nodes (0.01 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Clp0014I Perturbing problem by 0.001 % of 0.1 - largest nonzero change 0 (%
0) - largest zero change 0
Clp0006I 0  Obj -4721178 Primal inf 0.12781497 (23)
Clp0006I 0  Obj -4721178 Primal inf 0.12781497 (23)
Clp0006I 0  Obj -4721178 Primal inf 0.12781497 (23)
Clp0001I Primal infeasible - objective value -4721178
Cuts at root node changed objective from -4.72139e+006 to -4.72139e+006
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 - Problem proven infeasible

Objective value:
 100000000000000010000000000000000000000000000000000.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.01
Time (Wallclock seconds):       0.01

Total time (CPU seconds):       0.01   (Wallclock seconds):       0.01

And the output from GLPK:

GLPSOL: GLPK LP/MIP Solver, v4.52
Parameter(s) specified in the command line:
 --cuts --lp problem.lp
Reading problem data from `problem.lp'...
117 rows, 69 columns, 184 non-zeros
46 integer variables, all of which are binary
253 lines were read
GLPK Integer Optimizer, v4.52
117 rows, 69 columns, 184 non-zeros
46 integer variables, all of which are binary
Preprocessing...
23 constraint coefficient(s) were reduced
23 rows, 46 columns, 46 non-zeros
23 integer variables, all of which are binary
Scaling...
 A: min|aij| = 1.000e+000  max|aij| = 2.737e+003  ratio = 2.737e+003
GM: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
EQ: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
2N: min|aij| = 6.683e-001  max|aij| = 1.039e+000  ratio = 1.555e+000
Constructing initial basis...
Size of triangular part is 23
Solving LP relaxation...
GLPK Simplex Optimizer, v4.52
23 rows, 46 columns, 46 non-zeros
*     0: obj =  2.300000000e+001  infeas = 0.000e+000 (0)
*    46: obj =  4.721393495e+006  infeas = 0.000e+000 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Gomory's cuts enabled
MIR cuts enabled
Cover cuts enabled
Clique cuts enabled
Constructing conflict graph...
No conflicts found
+    46: mip =     not found yet <=              +inf        (1; 0)
+    46: >>>>>  4.721393495e+006 <=  4.721393495e+006   0.0% (1; 0)
+    46: mip =  4.721393495e+006 <=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (98120 bytes)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20140924/0aeba4a6/attachment.html>