[Cbc] Suboptimal solution as optimal?

Fri Dec 29 16:29:03 EST 2017

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=

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20171229/743eda6c/attachment-0001.html>