[Cbc] CBC reports infeasible, GLPK solves
John Forrest
john.forrest at fastercoin.com
Wed Sep 24 07:48:58 EDT 2014
Josh,
Unable to reproduce problem with Cbc 2.8 - all tries worked fine.
Would suggest upgrading as your version is nearly three years old.
John Forrest
On 24/09/14 12:32, Joshua Arnott wrote:
> 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)
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20140924/713d2194/attachment-0001.html>
More information about the Cbc
mailing list