5.6 Special Ordered Sets of Type 2

With a Special Ordered Set of type 1 you can select one option out of many. Usually the characteristics of the options are pre-defined and so the choice for each option is "take it or leave it". Special Ordered Sets of type 2 enable you to interpolate between the options. They are used to represent piecewise-linear functions of a decision variable. You can represent these as a series of linear relationships but if you use Linear Programming and there are economies of scale, the optimum LP solution will be to interpolate between zero and the largest (and most cost-effective) option. Defining the piecewise-linear function with a Special Ordered Set of type 2 and using Integer Programming forces the solution to lie on the function.

The definition of a Special Ordered Set of type 2 (S2 set) is very similar to that of an S1 set except that at most two adjacent members can be non-zero. The usual form in which it is found is where the sum of the members of the S2 set equals 1. In this case the members are conventionally represented by the symbol λ and we have the convexity constraint:

Σi λi = 1

Consider a variant of the factory problem. A decision must be made whether to expand the current factory or build a new one on a green-field site. Some back-of-the-envelope calculations have been made of various options. The costs against incremental capacity are shown in Figure 3.

Figure 3: Costs of Increasing Capacity

For a small increase in capacity it makes sense to expand the existing plant, but if a larger increase is required, it is better to build a new plant. Thus we have the curve shown in Figure 4 for the cost vs. incremental capacity.

Figure 4: Representing the Possibilities with an S2 Set

We could formulate this problem with binary variables as the only integer constructs. But the performance of the IP code will be much better if we use an S2 set. We identify a set of points {i = 1, 2, ... I} on the curve between which we are happy to interpolate linearly. Note that there are several points on the curve which we must represent:

  • "do nothing", i.e. zero increment of capacity and zero cost;
  • "do a little", i.e. a small increment of capacity at the existing plant and the fixed cost of making any change to the plant;
  • the "cross-over", where it becomes more economic to build a new plant rather than expand the existing one;
  • "do as much as possible", i.e. build as large a new factory as could be wanted.

How many other points should be represented is very much a matter of personal preference. Very often the data are of such quality that it is unlikely to be worth using more than a couple of further points We shall use a total of 6 points and denote the increments in capacity by CAPINCi and their costs by COSTi.

Suppose that we have a decision variable, x, which represents the capacity of the plant. We wish to relate it to y, the cost which we incur in making that capacity available. In other words, we wish to represent the function:

y = f(x)

We do this by relating x and y separately to a set of λ variables {λi} such that i λi = 1:

x = Σi XVALi λi

y = Σi YVALi λi

where XVALi, YVALi are the values of x and y at the point i between which we are interpolating. Suppose that the existing capacity of the factory is CAPOLD. Then for our factory expansion we must add to our formulation the rows:

x = CAPOLD + Σi CAPINCi λi

y = Σi COSTi λi

Σi λi = 1

with the requirement that the set {λi} forms an S2 set. We could take either of the first two rows as the reference row for the S2 set.

We can think of the λi variables as representing the "probability of choosing option i". That is, if λi = 1, we will choose option i. If λ3 = 0.25 and λ4 = 0.75 we shall have moved three-quarters of the way from option 3 to option 4, i.e. point A in Figure 4. Because of the restriction that at most two adjacent elements of the set can be non-zero, we cannot have the solution λi = 0.2, λi+2 = 0.8 or combinations in which three or more members of the set take non-zero values.

When we solve an IP problem, the first stage is to solve it as an LP and find the continuous solution. In this the integer restrictions are not observed. With the structure of cost vs incremental capacity shown in Figure 4, the optimal solution will lie on the line between points 1 and 6, i.e. the "do nothing" option and "do as much as possible". This is because this is the most "cost-effective" way of achieving any required level of capacity.

Suppose that the continuous solution lies at point P on the line between points 1 and 6. The model has decided to use an increment of capacity between CAPINC4 and CAPINC5 at a cost between COST3 and COST4. Now although this solution involves "cheating", it actually tells us a lot about what the real solution will be. The chances are that the model will actually want a solution somewhere between points 3 and 5, i.e. an increment of capacity between CAPINC3 and CAPINC5 at a cost between COST3 and COST5.

The beauty of the S2 set is that the IP code is able to focus in on these possibilities straightaway rather than spending its time on irrelevant branches. Without the S2 set, it is likely that the IP code would identify that the model didn't want to expand the existing factory and spend a lot of time branching variables representing different capacities of new factory. Only when it found these rather expensive might it reconsider the possibility of expanding the existing factory. The S2 set enables the model to see immediately that if it doesn't want to spend as much as COST4 it should expand the existing factory rather than building a new one.

We can now see what the reference row does. It provides the basis for the branching decisions which the IP code takes. If we specify the cost row as the reference row, the IP code will calculate the cost which the LP solution incurs in expanding the factory. It will then create two sub-problems based on spending more or less than this amount. If we specify the capacity row as the reference row, the IP code will calculate the capacity built and create two sub-problems based on creating more or less than this capacity.

S2 sets are very good at representing non-linear relationships between two continuous variables, as with cost and capacity here. If you can express the relationship as y = f(x), then an S2 set is likely to be as good a way of modelling it as you can achieve using IP. Having said that, it is not a panacea, and if the relationship involves a high degree of non-linearity, it may not be successful.

previous contents next

Comments