Special Ordered Sets

Basic functions

Special Ordered Sets of type n (n=1,2) are sets of variables of which at most n may be non-zero at an integer feasible solution. Associated with each set member is a real number (weight), establishing an ordering among the members of the set. In SOS of type 2, any positive variables must be adjacent in the sense of this ordering.

XPRBsos set1, set2;
XPRBarrvar s;

Immediate (ref. constraint)

XPRBctr c;
set1=XPRBnewsosrc(prob,"sA",XPRB_S2,s,c);

Immediate (coefficients)

double C[] = {1,2,3,4};
set2=XPRBnewsosw(prob,"sB",XPRB_S1,s,C);

Consecutive definition

set2=XPRBnewsos(prob,"sB",XPRB_S1);
XPRBaddsosarrel(set2,s,C);

Delete set definition

XPRBdelsos(set2);

Accessing sets

XPRBaddsosel(set2,s[2],4,5);
XPRBdelsosel(set1,s[0]);
XPRBgetsosname(set1);
XPRBgetsostype(set2);

Figure 3.2: Defining and accessing SOS: immediate (single function) by indicating a reference constraint; or consecutive definition by adding coefficients for all members.

In BCL, Special Ordered Sets may be defined in different ways as illustrated in Figure Defining and accessing SOS. As with arrays and constraints, they may be created either with a call to a single function (see Section Array-based SOS definition), or by adding coefficients consecutively.

In the basic, incremental definition, function XPRBnewsos marks the beginning of the definition of a set. Single members are added by function XPRBaddsosel and arrays by function XPRBaddsosarrel, each time indicating the corresponding coefficients. Single elements, or an entire set definition, can be deleted with functions XPRBdelsosel and XPRBdelsos respectively. BCL also has functions to retrieve the name of a SOS and its type (XPRBgetsosname and XPRBgetsostype). It is also possible to set branching directives for a SOS (function XPRBsetsosdir), including priorities, choice of the preferred branching direction and definition of pseudo costs.

Note:

all members that are added to a SOS must belong to the same problem as the SOS itself.

Array-based SOS definition

BCL provides two functions for creating Special Ordered Sets with a single function call: XPRBnewsosrc and XPRBnewsosw. With both functions, a new SOS is created by indicating the type (1 or 2), an array of variables and the corresponding weight coefficients for establishing an ordering among the set elements. With XPRBnewsosrc, these coefficients are taken from the variables' coefficients in the indicated reference constraint. When using function XPRBnewsosw, the user directly provides an array of weight coefficients.

Example

In the previous examples, instead of defining the delta variables as binaries, the problem can also be formulated using SOS of type 1. In this case, the delta variables are defined to be continuous as the SOS1 property and their unit sum ensure that one and only one takes the value one.

XPRBprob prob;                 /* BCL problem */
XPRBvar delta[NJ][NT];	       /* Variables for start times */
XPRBsos set[NJ];

void jobs_model(void)
{
 ...
 for(j=0;j<NJ;j++)             /*  Declare a variable for each job */
  for(t=0;t<NT-DUR[j]+1;t++)   /* and for each start time */
   delta[j][t] = XPRBnewvar(prob, XPRB_PL,
                            XPRBnewname("delta%d%d",j+1,t+1), 0, 1);
 for(j=0;j<NJ;j++)
 {                             /* Create a new SOS1 */
  set[j] = XPRBnewsos(prob, "sosj", XPRB_S1);
  for(t=0;t<NT-D[j]+1;t++)     /* Add variables to the SOS */
   XPRBaddsosel(set[j], delta[j][t], t+1);
 }
}

In order to simplify the definition of the SOS one can use the model formulation with variable arrays presented in the previous chapter. The constraints Link are employed as the reference constraints to determine the weight coefficient for each variable (the constraints need to be stored in an array, Link).

XPRBprob prob;                 /* BCL problem */
XPRBarrvar delta[NJ];	       /* Sets of var.s for start times  */
XPRBsos set[NJ];

void jobs_model(void)
{
 XPRBctr Link[NJ];             /* "Link" constraints */
 ...
 for(j=0;j<NJ;j++)             /*  Declare a set of var.s for each job */
  delta[j] = XPRBnewarrvar(prob, (NT-(int)DUR[j]+1), XPRB_PL,
                           XPRBnewname("delta%d",j+1), 0, 1);

 for(j=0;j<NJ;j++)             /* Linking start times & binaries  */
 {
  Link[j] = XPRBnewsumc(prob,"Link",delta[j],1,XPRB_E,0);
  XPRBaddterm(Link[j],start[j],-1);
 }

/* Create a SOS1 for each job using constraints "Link" as
   reference constraints */
 for(j=0;j<NJ;j++)
  set[j] = XPRBnewsosrc(prob, "sosj", XPRB_S1, delta[j], Link[j]);
}

Instead of setting directives on the binary variables, we may now define branching directives for the SOS1.

for(j=0;j<NJ;j++) XPRBsetsosdir(set[j],XPRB_DN,0);
                               /* First branch downwards on sets */