Binary variables become much more useful in Integer Programming when they are grouped together in A Special Ordered Set of type 1 (S1 set) consists of a set of binary variables δ 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 δ 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
However, the existence of a convexity row does not form part of the definition of an S1 set. |

LP Training > 5. Integer Programming >