[Cbc] Suboptimal solution as optimal?
John Forrest
john.forrest at fastercoin.com
Sat Dec 30 14:01:38 EST 2017
On big M - I was only trying to point out why the mini Branch and Bound
thought it had a solution (with a variable at 1.001) when it didn't.
After preprocessing the largest coefficient is about 3e8.
There probably could be more work done on topics such as SOS - I was in
at the birth of them and first used SOS type 2 in 70's (1970's)! There
are papers on branching on general disjunctions and SOS are just a
particular structured form.
John Forrest
On 30/12/17 18:13, Tobias Stengel wrote:
> Using SOS1 was not my idea. There is a post by Tobias Achterberg
> somewhere in the gurobi forum [1] about modelling indicator
> constraints mentioning that trick - I doubt it was first
> used/published there.
>
> There are also several posts about SOS1 vs Big-M in that forum,
> although I doubt that all details apply to CBC. In short they say if
> the M is suffient small, than Big-M is better due to the better
> relaxation. If M is to large, it will cause numerical issues and SOS1
> is better. Note that gurobi rewrites SOS to Big-M if it can derive a
> sufficient small M during presolve. I have no idea whether CBC does that.
>
> [1] https://groups.google.com/forum/#!forum/gurobi
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__groups.google.com_forum_-23-21forum_gurobi&d=DwQF-g&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=yjsiRUN9CzHHh3pEebw2XZCZewn_stfXq8wPhuyltzM&s=pSWe4v5OdzVpIGhv9x2cRKXZs8-WJ--eQZwvvzlGKcw&e=>
>
>
> ------------------------------------------------------------------------
> *Von:* Rhavar [rhavar at protonmail.com]
> *Gesendet:* Freitag, 29. Dezember 2017 23:26
> *An:* Bjørn Sigurd Johansen
> *Cc:* Tobias Stengel; cbc at list.coin-or.org
> *Betreff:* RE: [Cbc] Suboptimal solution as optimal?
>
> @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!
>>
>>
>> 1. How can a SOS1 constraint be defined in the model/lp text file?
>> 2. 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 <mailto: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
>> <mailto:john.forrest at fastercoin.com>
>>
>> To: cbc at list.coin-or.org <mailto: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 <mailto: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 <mailto: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=
>>
>>
>>
>>
>>
>
>
>
> _______________________________________________
> 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=yjsiRUN9CzHHh3pEebw2XZCZewn_stfXq8wPhuyltzM&s=ESRXK7OXcjFgREDPx_Lj3xnHVssB6iquAmm-PCtKT2M&e=
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20171230/203aad90/attachment-0001.html>
More information about the Cbc
mailing list