5.5 Sets of Decision Variables

Binary variables become much more useful in Integer Programming when they are grouped together in Special Ordered Sets. These represent the decision to select one option from many. What makes them much more powerful than simply a collection of binary variables is that they give more information to the Integer Programming algorithms and as a result the algorithms work better.

A Special Ordered Set of type 1 (S1 set) consists of a set of binary variables δi} such that at most one has a value greater than zero. It thus represents a multiple-choice problem: choose one of these or none at all. Accompanying the set there is a reference row. This is a row in which the members of the S1 set appear with coefficients which reflect some property of the various options, e.g. their cost or their size.

Consider an example in which a decision must be made as to whether to build a new factory and, if so, which one of several possibilities is to be built. The decision whether to build each possible factory is represented by the binary variables δ1, δ2, δ3, ... with δ0 used to represent "do nothing". Each factory has a capital cost and produces revenue benefits elsewhere in the model through increased production, greater efficiency, etc as shown in the chart below.

Figure 2: Cost vs Benefit for Options

In general we would expect that greater capital investment will result in greater benefits but there may well be diminishing returns as investment increases and anomalies (as with option 3 in the chart).

Intuitively we can see that the problem is really one of selecting the appropriate level of investment. It is thus closer to that of deciding the value of an integer variable x = 0, 1, 2, 3, ... than that of deciding individually the values of a number of binary variables. The IP algorithm follows this approach. It uses the continuous solution to help it to focus in quickly on the most likely options, thereby speeding the solution process.

IP codes differ in how much freedom they permit in the definition of sets. The most restrictive require:

  • sets to be disjoint;
  • exactly one element to be non-zero, and to take the value 1;
  • a specific row to be defined as the reference row for the set.
  • the members to be specified in order of increasing reference row entries;

Others allow:

  • decision variables which are members of more than one S1 set; this can be useful where you have a hierarchy of decisions;
  • there to be at most one (i.e. zero or one) non-zero member of the set, which can take a value less than some limit;
  • either no reference row to be defined or any row in the matrix can be defined as the reference row for any set so long as it has coefficients for all the members of the set. In particular the objective row often serves as the reference row for many sets;
  • the members of the set to be defined in any order, not just in order of increasing reference row entries.

In practice the most common use of S1 sets is to represent multiple-choice decisions, in which case there is a convexity row, :

Σi δi = 1

However, the existence of a convexity row does not form part of the definition of an S1 set.

previous contents next

Comments