AMPL SOS constraints

[Allison]

Hi, I'd like to be able to capture the following using an SOS1
constraint: At most one of x and y can be nonzero. Can anyone tell me
how to write this constraint in AMPL? An example of how to code an
SOS2 constraint in AMPL would also be helpful. Thank you!
--Allison

[Robert Fourer]

SOS1 is not relevant for "At most one of x and y can be nonzero." Rather,
if x and y are binary variables, use "x + y <= 1". More generally for x and
y nonnegative, define parameters xUP and yUP that are upper bounds on the
possible optimal values of x and y, define a binary variable b, and specify
the constraints "x <= xUP * b" and "y <= yUP * (1-b)".

Unless you have some very special situation, the best way to take advantage
of SOS2 is to use AMPL's piecewise-linear notation, which is automatically
converted to employ the SOS2 mechanism where appropriate.

Bob Fourer
4...@ampl.com

[Allison]

Could you tell me when SOS1 is relevant? Thanks,
--Allison

[Robert Fourer]

SOS1 is mainly relevant for models that restrict some variables to take a
value from an arbitrary list of values. As a simple example, you could
write

var Buy {f in FOODS} in {0,10,30,45,55};

If you are using CPLEX then the appropriate SOS1 representation will be
automatically generated from this declaration and you won't have to send any
specific SOS1 information yourself. I believe it works the same with
Gurobi.

It is possible to specify SOS1 variables and corresponding "reference rows"
explicitly using AMPL suffixes, as described in the solver documentation.
However this requires some study to understand whether SOS1 is appropriate
and how to apply it, and I don't recommend going to that trouble unless you
are having serious problems getting the solver to return a solution.

[Allison]

Thanks for your help!
--Allison

[Allison]

Hi, I am having trouble making the connection between SOS2 constraints
and AMPL's piecewise-linear notation. For example, if I wanted to
express the SOS2 constraint "at most two of w, x, y, and z can be
nonzero (and if two are nonzero, then they are adjacent)", what are
the breakpoints and slopes? I also don't understand how to capture the
adjacency variables. Any advice would be much appreciated.
Thank you!
--Allison

[Paul]

On Oct 5, 10:19 pm, Allison <allison.an.ch...@gmail.com> wrote:
> Hi, I am having trouble making the connection between SOS2 constraints
> and AMPL's piecewise-linear notation. For example, if I wanted to
> express the SOS2 constraint "at most two of w, x, y, and z can be
> nonzero (and if two are nonzero, then they are adjacent)", what are
> the breakpoints and slopes? I also don't understand how to capture the
> adjacency variables. Any advice would be much appreciated.

Any piecewise-linear function can be expressed as an SOS2 constraint,
where the variables in the constraint are weights used to create
convex combination of adjacent "corners" in the graph of the pw-linear
function. AMPL supports that if the solver knows about SOS2
constraints. Not every SOS2 constraint necessarily corresponds to a
piecewise-linear function, however (although pw-linear functions, or
pw-linear approximations to nonlinear functions, are the only times I
recall seeing SOS2 used). I don't think AMPL directly supports more
general SOS2 constraints.

/Paul

[Allison]

I see. In this case, it would be helpful if I could see an example of
how to express an SOS2 constraint using suffixes. For example, if I
wanted to capture "at most two adjacent variables from w, x, y, and z
can be nonzero", could I write the following:

let w.sosno:=-1;
let x.sosno:=-1;
let y.sosno:=-1;
let z.sosno:=-1;

I'm not sure what the ref suffixes mean. It doesn't seem to work when
I try something like:

let w.ref:=1;
let x.ref:=2;
let y.ref:=3;
let z.ref:=4;

Thanks!
--Allison

[Paul]

On Oct 6, 1:25 pm, Allison <allison.an.ch...@gmail.com> wrote:
> I see. In this case, it would be helpful if I could see an example of
> how to express an SOS2 constraint using suffixes. For example, if I
> wanted to capture "at most two adjacent variables from w, x, y, and z
> can be nonzero", could I write the following:
>
> let w.sosno:=-1;
> let x.sosno:=-1;
> let y.sosno:=-1;
> let z.sosno:=-1;
>
> I'm not sure what the ref suffixes mean. It doesn't seem to work when
> I try something like:
>
> let w.ref:=1;
> let x.ref:=2;
> let y.ref:=3;
> let z.ref:=4;
>

I assume you declared the .ref and .sosno suffixes before using them?
suffix sosno integer IN;
suffix ref integer IN;

I seem to be able to produce the desired behavior. Consider the
following model, which mimics what you have:

var w integer >= 0 <= 3;
var x integer >= 0 <= 3;
var y integer >= 0 <= 3;
var z integer >= 0 <= 3;
maximize Obj: w + 2*x + 0.5*y + 3*z;
s.t. C1: w + x + y + z <= 5;
option solver cplexamp;
suffix sosno integer IN;
suffix ref integer IN;
let w.sosno := -1;
let x.sosno := -1;
let y.sosno := -1;
let z.sosno := -1;
let w.ref := 1;
let x.ref := 2;
let y.ref := 3;
let z.ref := 4;
solve;
display w, x, y, z;

If I comment out the four statements assigning .ref values, I get a
solution that ignores the SOS2 restriction and uses x and z. With
those statements included, I get a correct solution (objective value
inferior to the previous one) that adheres to the SOS2 constraint and
uses y and z. If I change w.ref to 5 (changing the variable order to
x, y, z, w), I get a different solution that uses w and z.

/Paul

[Allison]

Thanks so much for your help, Paul. I think the problem might be
coming from the SOS1 constraints I'm trying to include using suffixes.
For example,

let s.sosno:=1;
let t.sosno:=1;

Even if I leave out the ref suffixes, I get the following error:

CPXcopysos failed; error code 3010

I don't know what could be causing this error.
Thanks again,
--Allison

[Paul]

On Oct 8, 2:48 pm, Allison <allison.an.ch...@gmail.com> wrote:
> Thanks so much for your help, Paul. I think the problem might be
> coming from the SOS1 constraints I'm trying to include using suffixes.
> For example,
>
> let s.sosno:=1;
> let t.sosno:=1;
>
> Even if I leave out the ref suffixes, I get the following error:
>
> CPXcopysos failed; error code 3010
>
> I don't know what could be causing this error.

What version of CPLEX are you using? Error code 3010 has something to
do with the weights for the SOS variables not being unique, but I'm
unable to produce that error in CPLEX 12.2 even if I default all the
weights to zero (which makes me think that perhaps there has been a
change to how CPLEX handles SOS constraints, even though the docs
still indicate you need unique weights). If you take my example from
my previous response and change all the .sosno values to +1 (to make
it a type 1 SOS), what happens with 12.2 is that I get a correct
answer as long as at least one .ref value is nonzero (even if they are
all equal, or if all but one are commented out), and an incorrect
answer (but not a CPLEX error) if they are omitted (which means all
default to 0) or if those that are not omitted are all assigned value
0.

In any event, try assigning unique values to s.ref and t.ref and see
if it works for you.

/Paul

[Allison]

I realized what I did wrong. My actual problem has a lot of variables,
and in looping through them to set the sosno suffixes, I indexed the
same variable twice and thus gave it two different sosno values. I'm
not getting the error anymore. Thanks, Paul, for all of your advice.

One more question about SOS constraints: Can anyone tell me what
effect the ref values have besides capturing adjacency? For example,
if I used 5, 6, 7, 8 instead of 1, 2, 3, 4 for the ref values in my
example above, is that supposed to affect the solution? Do the ref
values somehow tell the solver to branch more on certain variables
than on others?
Thanks!
--Allison

[Paul]

On Oct 12, 2:43 pm, Allison <allison.an.ch...@gmail.com> wrote:
>
> One more question about SOS constraints: Can anyone tell me what
> effect the ref values have besides capturing adjacency? For example,
> if I used 5, 6, 7, 8 instead of 1, 2, 3, 4 for the ref values in my
> example above, is that supposed to affect the solution? Do the ref
> values somehow tell the solver to branch more on certain variables
> than on others?

In SOS1 sets, the weights are used to establish an order for the
variables. I'm not positive, but I believe that the conventional use
for the weights is that the solver branches on an SOS1 constraint by
splitting the variables (or those variables not already fixed at zero)
into two groups of roughly equal cardinality, using the weights to
dictate the order. In each child node, all variables in one of the
two subsets are fixed to zero. When the variables are binary (which
is usually the case), it's also possible that the solver might split
into two subsets of roughly equal total weight (which could mean
unequal cardinality). I'm not sure if any solvers do that, but I
vaguely recall seeing a mention of it somewhere many years ago (might
have just been speculating on it as a possible alternative branching
rule).

/Paul

[Robert Fourer]

Branching on a special ordered set involves splitting it into progressively
smaller subsets, and the reference values are used to determine where the
split should occur. In general, the subsets determined by use of the
reference values are not of the same size.

When a SOS of type 1 is used to model a variable that must take a value from
some arbitrary finite set, the reference values are the values in that set.
When a SOS of type 2 is used to model a piecewise-linear function of a
variable, the reference values are the breakpoints of the piecewise-linear
function.

If you look back at the original paper on the subject, which you can find at
www.thetomlins.org/sos.pdf, you will see that these are the modeling
situations that SOS1 and SOS2 were primarily intended for. Thus AMPL was
designed to express these situations naturally in terms of the original
variables, with the auxiliary SOS variables, reference values, etc. being
set up automatically behind the scenes. If you want to use SOS1 or SOS2 for
other situations, by setting them up explicitly using .sosno and .ref
suffixes, then you need to determine on your own what reference values to
specify in order to get the best performance for your problems.

Bob Fourer
4...@ampl.com

> -----Original Message-----
> From: am...@googlegroups.com [mailto:am...@googlegroups.com]
> On Behalf Of Paul
> Sent: Tuesday, October 12, 2010 3:02 PM
> To: AMPL Modeling Language

> --
> You received this message because you are subscribed to the Google
> Groups "AMPL Modeling Language" group.
> To post to this group, send email to am...@googlegroups.com.
> To unsubscribe from this group, send email to
> ampl+uns...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/ampl?hl=en.