[Cbc] Suboptimal solution as optimal?

Sat Dec 30 13:03:21 EST 2017

Hi,

I think it is not possible to specify SOS1 in .LP or .MPS files.
Anyway, the default CBC pre-preprocessing routine searchers for SOS
structures :
Coin:preprocess
<Possible options for preprocess are: off on save equal sos trysos equalall
strategy aggregate
forcesos;
       current  sos>

Cheers,

On Fri, Dec 29, 2017 at 7:29 PM, Bjørn Sigurd Johansen (Spider Solutions
AS) <bjorn.sigurd.johansen at spidersolutions.no> wrote:

> 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
> *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=
>
>
>
>
>
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> https://list.coin-or.org/mailman/listinfo/cbc
>
>

-- 
=============================================================
Haroldo Gambini Santos
Computing Department
Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ] iceb.ufop.br
home/research page: www.decom.ufop.br/haroldo

It has long been an axiom of mine that the little things are infinitely
the most important.
-- Sir Arthur Conan Doyle, "A Case of Identity"
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20171230/1d99e9a3/attachment-0001.html>