[Cbc] SOS constraints

[Miles Lubin]

Hi John,

Just to follow up on this, for
Maximize  5x[1] + 3x[2] + 2x[3] + 7x[4] + 4x[5]
     s.t.     SOS1(x[1],x[2],x[3],x[4],x[5])
               All x binary
Cbc is returning an optimal objective 21. If SOS1 imposes that at most one
is nonzero, then I would've expected all x[i] = 0, except for x[4] =1 as
the optimal solution. Am I doing something wrong?

You can see the test code here:
https://projects.coin-or.org/Cbc/browser/trunk/Cbc/test/CInterfaceTest.c?rev=2039#L195
and the SOS C wrapper here:
https://projects.coin-or.org/Cbc/browser/trunk/Cbc/src/Cbc_C_Interface.cpp?rev=2039#L773

Thanks,
Miles


On Fri, May 9, 2014 at 12:56 PM, Miles Lubin <miles.lubin at gmail.com> wrote:

> Hi John,
>
> Thanks for the clarification. When I change the problem sense to
> maximize, however, the solution returned is all ones, so the SOS
> constraint doesn't seem to be enforced in the way that you described.
> It's possible that it's not being added correctly in the C interface,
> though.
>
> Best,
> Miles
>
> On Fri, May 9, 2014 at 2:54 AM, John Forrest
> <john.forrest at fastercoin.com> wrote:
> > Miles,
> >
> > Definition of SOS type 1 that is used is that at most one in set nonzero.
> > If more than one then you create two branches around a point in set and
> one
> > branch sets all one side to zero and the other branch sets the other
> side to
> > zero.
> >
> > So in this case you do need the equality constraint.
> >
> > John Forrest
> >
> > On 08/05/14 18:50, Miles Lubin wrote:
> >>
> >> Hi all,
> >>
> >> I just tried to clean up and test SOS constraints in the new C
> >> interface. My test problem is:
> >>
> >> Minimize  5x[1] + 3x[2] + 2x[3] + 7x[4] + 4x[5]
> >>       s.t.       x[1] +  x[2] +  x[3] +  x[4] +  x[5] == 1
> >>                 All x binary
> >>
> >> I have not added the equality constraint explicitly to the model, but
> >> instead added an SOS 1 constraint. When I solve, the solution is zero,
> >> so the SOS 1 constraint doesn't seem to be enforced. Is adding the SOS
> >> object to the model sufficient to enforce the constraint, or is it
> >> purely for branching?
> >>
> >> Test code:
> >>
> https://projects.coin-or.org/Cbc/browser/trunk/Cbc/test/CInterfaceTest.c?rev=2033#L113
> >> Implementation of Cbc_addSOS in the C interface:
> >>
> >>
> https://projects.coin-or.org/Cbc/browser/trunk/Cbc/src/Cbc_C_Interface.cpp#L827
> >>
> >> Thanks,
> >> Miles
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20140619/73c60815/attachment.html>