[Cbc] Cbc returns invalid result on simple problem unless presolve is enabled

[Stefan Hacker]

Hello John and Giacomo,

thanks a lot to both of you. I definitely did not intend to trick the
solver. Natural talent I guess ;) Thanks to John's explanation I now
understand how this went wrong and why cbc couldn't notice it. I agree
that making the model better would be ideal. For now I implemented the
workaround described by John until I can figure that out. I assume
turning off scaling and adjusting the tolerance might get me into
trouble in some other way depending on the values? I could not find
any specifics on that in the documentation.

Do you have any suggestions on material I can use to learn about what
properties make a model numerically difficult and how to
(re-)formulate it to prevent these issues in the future?

Thanks again. Getting such useful help so quickly was great.

Regards,
Stefan

On 18 November 2016 at 10:18, John Forrest <john.forrest at fastercoin.com> wrote:
> Giacomo (and Stefan),
>
> I agree that improving the numerical properties would be a good idea.
>
> Allan Wechsler has pointed out to me that there is an integer tolerance
> which could be set to a smaller value.  This can not be set from the
> standalone cbc, but can be from the example drivers -
> model.setIntegerTolerance(1.0e-10).
>
> Just doing that does not not fix the problem, but also turning off scaling
> does.
>
> John Forrest
> On 17/11/16 15:17, Giacomo Nannicini wrote:
>
> Hi John and Stefan,
> I would hardly call this a bug. The model is ill-conditioned
> (coefficients ranging from 10^-2 to 10^7) and it almost seems
> specifically built to 'trick" a solver into problems. The commercial
> solver CPLEX has exactly the same behavior: if preprocessing is
> disabled, it returns a solution with value 1000. So I do not think
> there is much that can be done, other than trying to improve the
> numerical properties of the model.
>
> GiacomoAllan Wechsler
>
> On Thu, Nov 17, 2016 at 6:36 AM, John Forrest
> <john.forrest at fastercoin.com> wrote:
>
> Stefan,
>
> It is a bug, but I am not sure how to fix.
>
> The optimal continuous solution is 0.0,1.0e-9,0.0.  These values are all
> within integer tolerances so it sets to integers i.e. 0,0,0 and thinks that
> as the continuous solution is integral then the search is over and fixes
> integer variable to 0 and leaves others .  However while the continuous
> objective value was 9.0e-10, the  new solution will be 1.0e-3,0.0,0.0 -
> giving an objective value of 1000.
>
> The fixes that I can think of would affect performance too much and/or be
> complicated.
> On 16/11/16 09:09, Stefan Hacker wrote:
>
> Hi,
>
> I am trying to use Cbc to solve what I thought to be a simple problem.
> However the behavior I see makes me wonder if I am encountering a Cbc
> bug or if there is something wrong in the way I am using it.
>
> If I run the attached model using Cbc 2.9.7 (version isn't that
> important I think) from the console like this:
> cbc model.lp -solve
>
> I get the expected objective value of 0.9. However without presolving
> enabled
> cbc model.lp -preprocess off -solve
>
> Cbc returns an objective value of 1000 which is incorrect.
>
> Originally I was using Cbc as a library (close to the minimum.cpp
> example from the documentation) and didn't consider presolve to be
> relevant for such a small problem. Activating it feels like I am just
> suppressing a symptom without understanding or fixing the cause. Even
> more confusing to me is that after the call to branchAndBound the
> CbcModel returns 0 for primary and secondary status and
> isProvenOptimal returns true.
>
> Is the result being wrong without presolve a bug or am I trying
> something stupid here without noticing? Also Cbc returning "optimal"
> in all ways I know to check but still returning an incorrect result is
> unsettling. Did I miss some indicator Cbc gave me?
>
> Thanks a lot.
>
> Regards,
> Stefan
>
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=FlCDUkCFyl6LUVRWa6Mu7ehYk1QuoUvgFPJh_u4AQ-4&s=sSI8pGvVrbw0LJd5V9yjX8yTc8fpKvA0GSiLH77xu2c&e=
>
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=8FaVxIx99H879Ebkij38NpcRZoYLK-7QMl1LqyvBccA&m=fJ6JENZYx2k6pJo0f5S4KxtatK98Kji6H7IG4z1t5rk&s=GZXssk61y1TSxW4GAKGZzmDUkWHg__fPQFQgvzZbV1c&e=
>
>
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> https://urldefense.proofpoint.com/v2/url?u=http-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=CwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=x70aravj5YfMPjlspgnttdtArBmc0FFvbWhCQD6FKM8&m=QieYyZ7NS2bRnjqjW8yQ38NFWSB4vNCapi9sdNcV0Hg&s=PBwScEC628WefihdeF29AMVBdddDM7mmZhdZI9E-gY0&e=
>