How can I use the solver’s “special ordered sets” feature?

FAQs
1

There are two kinds of formulations that cause special ordered sets to be set up by AMPL and used by your solver automatically. For other situations you can explicitly identify special ordered sets of types 1 and 2 using certain suffixes on variables. The first kind of formulation involves variables that are restricted to a finite but not regularly-spaced series of values. For example, each variable Cap[j] standing for the capacity of warehouse j might be required to take one of the values in a given set S by use of a declaration like this:

var Cap {i in WHSE} in S;

(For example, S might contain only 0, 15, 25, and 30.) Special ordered sets of type 1 are automatically generated to help the solver branch efficiently on the possibilities in this case. The second kind of formulation is used to handle separable piecewise-linear functions written as described in Chapter 17 of the AMPL book. As an example, a 3-part shipment cost to be minimized may be written as

minimize Total_Cost: 
     sum {i in ORIG, j in DEST}
        <<limit1[i,j],limit2[i,j]; 
          rate1[i,j], rate2[i,j], rate3[i,j] >> Trans[i,j];

using AMPL’s <<>> notation for writing piecewise-linear functions in terms of their breakpoints and slopes. In special cases there is an equivalent linear formulation; but in all other cases, special ordered sets of type 2 are automatically generated to help the solver search the possibilities. To identify special ordered sets explicitly, the following statements must first be used to create two suffixes for providing extra information on each variable:

suffix sosno integer IN; 
suffix ref integer IN;

For our type 1 example above, auxiliary binary variables Lambda[i,j] could be defined to express the Cap[i] variables as sums that can only take on the possible values in S :

param nWhse integer > 0; 
set WHSE = 1..nWhse; 
var Lambda {i in WHSE, j in S} binary; 
var Cap {i in WHSE} = sum {j in S} j * Lambda[i,j]; 
subject to ChooseOne {i in WHSE}: 
   sum {j in S} Lambda[i,j] = 1;

The special ordered sets for this formulation could be defined by assigning values to the suffixes as follows:

let {i in WHSE, j in S} Lambda[i,j].sosno := i; 
let {i in WHSE, j in S} Lambda[i,j].ref := j;

The variables in each special ordered set must be given the same unique .sosno value, positive for sets of type 1 or negative for sets of type 2. The .ref values guide branching within the solver’s branch-and-bound scheme, and are generally the coefficients in a sum like sum {j in S} j * Lambda[i,j] that appears in the definition of some variable. The details vary with the situation being modeled, and some advanced study of relevant papers may be necessary to get them right.