[Cbc] Suboptimal solution as optimal?

Wed Dec 27 19:09:21 EST 2017

I'm running a later version:

$ cbc --version

Welcome to the CBC MILP Solver

Version: 2.9.6

Build Date: Dec 22 2017

and it's not core-dumping or marking the problem as infeasible (whic it's not)

-Ryan

> -------- Original Message --------
> Subject: Re: [Cbc] Suboptimal solution as optimal?
> Local Time: December 27, 2017 3:03 PM
> UTC Time: December 27, 2017 9:03 PM
> From: rod at frowd.net
> To: Rhavar <rhavar at protonmail.com>, cbc at list.coin-or.org <cbc at list.coin-or.org>
>
> Which version of cbc are you running? It is solving to the optimal and then core dumping?
>
> cbc -import problem.lp -min -solve
> Welcome to the CBC MILP Solver
> Version: 2.8.12
> Build Date: Feb 22 2016
>
> command line - cbc -import problem.lp -min -solve (default strategy 1)
> Continuous objective value is 0 - 0.00 seconds
> Cgl0003I 0 fixed, 9 tightened bounds, 1 strengthened rows, 0 substitutions
> Cgl0004I processed model has 7 rows, 164 columns (164 integer) and 636 elements
> Cutoff increment increased from 1e-05 to 0.9999
> Cbc0038I Pass   1: suminf.    0.30901 (2) obj. 70.3063 iterations 3
> Cbc0038I Solution found of 70.3063
> Cbc0038I Branch and bound needed to clear up 2 general integers
> Cbc0038I Full problem 7 rows 164 columns, reduced to 4 rows 25 columns
> Cbc0038I Cleaned solution of 31480
> Cbc0038I Before mini branch and bound, 160 integers at bound fixed and 0 continuous
> Cbc0038I Mini branch and bound improved solution from 31480 to 31480 (0.04 seconds)
> Cbc0038I Round again with cutoff of 28331.1
> Cbc0038I Pass   2: suminf.    0.30901 (2) obj. 70.3063 iterations 0
> Cbc0038I Solution found of 70.3063
> Cbc0038I Branch and bound needed to clear up 2 general integers
> Cbc0038I Full problem 8 rows 164 columns, reduced to 4 rows 14 columns
> Cbc0038I Mini branch and bound could not fix general integers
> Cbc0038I No solution found this major pass
> Cbc0038I Before mini branch and bound, 160 integers at bound fixed and 0 continuous
> Cbc0038I Mini branch and bound did not improve solution (0.04 seconds)
> Cbc0038I After 0.04 seconds - Feasibility pump exiting with objective of 31480 - took 0.02 seconds
> Cbc0012I Integer solution of 31480 found by feasibility pump after 0 iterations and 0 nodes (0.04 seconds)
> Cbc0038I Full problem 7 rows 164 columns, reduced to 3 rows 5 columns
> Cbc0038I Full problem 7 rows 164 columns, reduced to 2 rows 3 columns
> Cbc0031I 3 added rows had average density of 91.666667
> Cbc0013I At root node, 3 cuts changed objective from 0 to 0 in 38 passes
> Cbc0014I Cut generator 0 (Probing) - 1 row cuts average 2.0 elements, 2 column cuts (2 active)  in 0.052 seconds - new frequency is -100
> Cbc0014I Cut generator 1 (Gomory) - 49 row cuts average 162.6 elements, 0 column cuts (0 active)  in 0.016 seconds - new frequency is -100
> Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
> Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
> Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 43 row cuts average 140.8 elements, 0 column cuts (0 active)  in 0.004 seconds - new frequency is -100
> Cbc0014I Cut generator 6 (TwoMirCuts) - 14 row cuts average 150.1 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
> Cbc0010I After 0 nodes, 1 on tree, 31480 best solution, best possible 0 (0.14 seconds)
> Cbc0016I Integer solution of 11580 found by strong branching after 238 iterations and 20 nodes (0.15 seconds)
> Cbc0038I Full problem 7 rows 164 columns, reduced to 7 rows 8 columns
> Cbc0038I Full problem 7 rows 164 columns, reduced to 6 rows 7 columns
> Cbc0016I Integer solution of 8600 found by strong branching after 474 iterations and 87 nodes (0.18 seconds)
> Cbc0038I Full problem 7 rows 164 columns, reduced to 7 rows 9 columns
> Cbc0038I Full problem 7 rows 164 columns, reduced to 4 rows 7 columns
> Cbc0012I Integer solution of 1025 found by RINS after 482 iterations and 91 nodes (0.19 seconds)
> Cbc0038I Full problem 7 rows 164 columns, reduced to 7 rows 12 columns
> Cbc0012I Integer solution of 825 found by combine solutions after 482 iterations and 91 nodes (0.19 seconds)
> Cbc0038I Full problem 7 rows 164 columns, reduced to 3 rows 7 columns
> Cbc0004I Integer solution of 70 found after 1719 iterations and 372 nodes (0.27 seconds)
> Cbc0038I Full problem 7 rows 164 columns, reduced to 7 rows 13 columns
> Cbc0038I Full problem 7 rows 164 columns, reduced to 4 rows 8 columns
> cbc: CbcModel.cpp:15284: int CbcModel::doOneNode(CbcModel*, CbcNode*&, CbcNode*&): Assertion `feasible' failed.
> Aborted (core dumped)
>
> On 28/12/2017 5:58 AM, Rhavar wrote:
>
>> I just realized, an easy way to prove the solver is finding a suboptimal solution is by forcing it's hand and adding an additional constraint:
>>
>> force: i22 = 1
>>
>> and you will see it returns a better solution that it didn't see before
>>
>> -Ryan
>>
>>> -------- Original Message --------
>>> Subject: Suboptimal solution as optimal?
>>> Local Time: December 27, 2017 12:37 PM
>>> UTC Time: December 27, 2017 6:37 PM
>>> From: rhavar at protonmail.com
>>> To: cbc at list.coin-or.org [<cbc at list.coin-or.org>](mailto:cbc at list.coin-or.org)
>>>
>>> I have a problem:
>>> https://gist.github.com/RHavar/dfb9de631363ecb9e1c326fff5ebd09b
>>>
>>> (lp file and solution file attached)
>>>
>>> In the solution it says: "Optimal - objective value"  but I think I have found a superior solution by hand:
>>>
>>>  o6 = 1
>>> i22 = 1
>>>
>>> Which gives a better objective (70 instead of 825)
>>>
>>> --
>>>
>>> So I guess my question is, does "Optimal - objective value"  mean that it's guaranteed to be the optimal solution? Or am I doing something wrong? Or is there a bug in cbc?
>>>
>>> -Ryan
>>
>> _______________________________________________
>> Cbc mailing list
>> Cbc at list.coin-or.org
>>
>> https://list.coin-or.org/mailman/listinfo/cbc
>
> https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient
> Virus-free. [www.avast.com](https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient)
>
> #DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20171227/3bc8e971/attachment-0001.html>