[Cbc] Suboptimal solution as optimal?

Fri Dec 29 17:26:37 EST 2017

@Tobias Stengel    Wow! Thanks, you're a genius. That works fantastically.

@Bjørn Sigurd Johansen

I'm no expert (i learnt about them an hour ago). But adding a section:

SOS
  set1: S1:: no_change:1 change_amount:2

at the end (before "end") works for me.

Also I don't think your constraint makes sense, as it would force everything to always be 0.

-Ryan

> -------- Original Message --------
> Subject: RE: [Cbc] Suboptimal solution as optimal?
> Local Time: December 29, 2017 3:29 PM
> UTC Time: December 29, 2017 9:29 PM
> From: bjorn.sigurd.johansen at spidersolutions.no
> To: Tobias Stengel <Tobias.Stengel at locom.de>, Rhavar <rhavar at protonmail.com>
> cbc at list.coin-or.org <cbc at list.coin-or.org>
>
> Hi!
>
> - How can a SOS1 constraint be defined in the model/lp text file?
>
> - Is a SOS1 constraint handled more efficiently than a constraint of type
>
> MyBinaryVariable1 + MyBinaryVariable2 + … + MyBinaryVariableN <=0                 ?
>
> Best regards,
>
> Bjørn Sigurd
>
> From: Cbc [mailto:cbc-bounces at coin-or.org] On Behalf Of Tobias Stengel
> Sent: fredag 29. desember 2017 21:49
> To: Rhavar <rhavar at protonmail.com>
> Cc: cbc at list.coin-or.org
> Subject: Re: [Cbc] Suboptimal solution as optimal?
>
> You can use a SOS1:
> First add a binary variable "has_no_change" and add the constraint
> has_no_change + has_change = 1
> Then your c1 can be replaced with a SOS1 containing change_amount and has_no_change.
>
> If you need to force has_change = 0 if change_amount = 0 you still need c0 (or something similar). Often this is not necessary, e.g. if has_change does not show up in any other constraint and has a positive coefficient in the objective (assuming minimization).
>
> ---------------------------------------------------------------
>
> Von: Cbc [cbc-bounces at coin-or.org]" im Auftrag von "Rhavar [rhavar at protonmail.com]
> Gesendet: Freitag, 29. Dezember 2017 16:04
> An: John Forrest
> Cc: cbc at list.coin-or.org
> Betreff: Re: [Cbc] Suboptimal solution as optimal?
>
> A bit of a tangent, but the reason the model is "not well scaled" is because I have two variables:
>
> change_amount    (a number saying how much change will be created)
>
> has_change  (a binary 0 or 1, saying if there's change)
>
> and I need to constrain these two things together.  The only way I could think of was by creating two different constraints:
>
> c0: + change_amount - has_change >= 0
>
> c1: + 2100000000000000 has_change - change_amount >= 0
>
> Which in a high level language would be:
>
> let has_change = change_amount > 0
>
> (the reason I use 2.1e14 is because it's a max theoretical amount change could ever be. Although in practice, it's several orders of magnitude less).
>
> Is there a smarter way of doing what I'm trying to do?
>
> ---
>
> -Ryan
>
>> -------- Original Message --------
>>
>> Subject: Re: [Cbc] Suboptimal solution as optimal?
>>
>> Local Time: December 29, 2017 4:39 AM
>>
>> UTC Time: December 29, 2017 10:39 AM
>>
>> From: john.forrest at fastercoin.com
>>
>> To: cbc at list.coin-or.org
>>
>> Fixed hopefully - stable and trunk.
>>
>> The original model is not well scaled - one element was 2.1e14 and even after preprocessing the problem had to be solved applying scaling factors.  The small fast branch and bound is deliberately a bit forgiving on this.  When the code thinks it has got a solution it double checks.  In this case it did that and threw that solution out - but it had left some variables fixed when they should not have been.
>>
>> John Forrest
>>
>> On 28/12/17 18:30, John Forrest wrote:
>>
>>> Ryan,
>>>
>>> Bug in Cbc.  My first try gave correct result, but I managed to get error.  For small problems, Cbc will do a simpler faster branch and bound on a portion of the tree.  This is returning infeasible - I will look into it.
>>>
>>> If you add -depth -100 (which means only go into this simpler version at depth 100) then all looked fine.
>>>
>>> John Forrest
>>>
>>> On 27/12/17 18:37, Rhavar wrote:
>>>
>>>> I have a problem:
>>>>
>>>> [https://gist.github.com/RHavar/dfb9de631363ecb9e1c326fff5ebd09b](https://urldefense.proofpoint.com/v2/url?u=https-3A__gist.github.com_RHavar_dfb9de631363ecb9e1c326fff5ebd09b&d=DwMDaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=S4VZrfTJ9vrNsPyEyqDoTZUqb0eG9rdZ8l7-jr8EA9Y&s=dWErV9QjwaNhpQZZkV1ZmdJ_Ofpqgb80lh0-5ORAiSU&e=)
>>>>
>>>> (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://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwMDaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=S4VZrfTJ9vrNsPyEyqDoTZUqb0eG9rdZ8l7-jr8EA9Y&s=SVcz-BvCf0RgvZrRQQxyV89AGoSkVGhfQhv4tx1JKV4&e=)
>>>
>>> _______________________________________________
>>>
>>> Cbc mailing list
>>>
>>> Cbc at list.coin-or.org
>>>
>>> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=S4VZrfTJ9vrNsPyEyqDoTZUqb0eG9rdZ8l7-jr8EA9Y&s=SVcz-BvCf0RgvZrRQQxyV89AGoSkVGhfQhv4tx1JKV4&e=
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20171229/749fa057/attachment-0001.html>