The project planning model using Special Ordered Sets

The example can be modified to use Special Ordered Sets of type 1 (SOS1). The start_pm variables for a given p form a set of variables which are ordered by m, the month. The ordering is induced by the coefficients of the start_pm in the specification of the SOS. For example, start_p1's coefficient, 1, is less than start_p2's, 2, which in turn is less than start_p3's coefficient, and so on The fact that the start_pm variables for a given p form a set of variables is specified to Mosel as follows:

(! Define SOS-1 sets that ensure that at most one start(p,m) is non-zero
   for each project p. Use month index to order the variables !)

 forall(p in PROJ) XSet(p):= sum(m in MONTHS) m*start(p,m) is_sos1

The is_sos1 specification tells Mosel that Xset(p) is a Special Ordered Set of type 1. The linear expression specifies both the set members and the coefficients that order the set members. It says that all the start_pm variables for m in the MONTHS index range are members of an SOS1 with reference row entries m.

The specification of the start_pm as binary variables must now be removed. The binary nature of the start_pm is implied by the SOS1 property, since if the start_pm must add up to 1 and only one of them can differ from zero, then just one is 1 and the others are 0.

If the two formulations are equivalent why were Special Ordered Sets invented, and why are they useful? The answer lies in the way the reference row gives the search procedure in Integer Programming (IP) good clues as to where the best solution lies. Quite frequently the Linear Programming (LP) problem that is solved as a first approximation to an Integer Program gives an answer where start_p1 is fractional, say with a value of 0.5, and start_p,NM takes on the same fractional value. The IP will say:

`my job is to get variables to 0 or 1. Most of the variables are already there so I will try moving xp1 or xpT. Since the set members must add up to 1.0, one of them will go to 1, and one to 0. So I think that we start the project either in the first month or in the last month.'

A much better guess is to see that the start_pm are ordered and the LP solution is telling us it looks as if the best month to start is somewhere midway between the first and the last month. When sets are present, the IP can branch on sets of variables. It might well separate the months into those before the middle of the period, and those later. It can then try forcing all the early start_pm to 0, and restricting the choice of the one start_pm that can be 1 to the later start_pm. It has this option because it now has the information to `know' what is an early and what is a late start_pm, whereas these variables were unordered in the binary formulation.

The power of the set formulation can only really be judged by its effectiveness in solving large, difficult problems. When it is incorporated into a good IP system such as Xpress it is often found to be an order of magnitude better than the equivalent binary formulation for large problems.