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
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
CAPINC 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:
We do this by relating x and y separately to a set of λ variables {λ
where XVAL
with the requirement that the set {λ We can think of the λ 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
CAPINC 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 COST 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. |

LP Training > 5. Integer Programming >