Example: SOS Type 1 for Sizing a Warehouse
To give you a feel for how SOS can be useful, here's an example of an SOS Type 1 used to choose the size of a warehouse. Let's assume for this example that we can build a warehouse of 10000, 20000, 40000, or 50000 square feet. We define binary variables for the four sizes, say, x1, x2, x4, and x5. We connect these variables by a constraint defining another variable to denote available square feet, like this: z - 10000x1 - 20000x2 - 40000x4 - 50000x5 = 0.
Those four variables are members of a special ordered set. Only one size can be chosen for the warehouse; that is, at most one of the x variables can be nonzero in the solution. And, there is an order relationship among the x variables (namely, the sizes) that can be used as weights. We say that the weights of the set members are 10000, 20000, 40000, and 50000.
Let's say furthermore that we have a fractional (that is, noninteger) solution of x1 = 0.1, x5 = 0.9. These values indicate that other parts of the model have imposed the requirement of 46000 square feet since 0.1*10000 + 0.9*50000 = 46000. In SOS parlance, we say that the weighted average of the set is (0.1*10000 + 0.9*50000)/(0.1 + 0.9) = 46000.
We split the set before the variable with weight exceeding the weighted average. In this case, we split the set like this: x1, x2, and x4 will be in one subset; x5 in the other.
Now we branch. One branch restricts x1, x2, x4 to 0 (zero). This branch results in x5 being set to 1 (one).
The other branch, where x5 is set to 0 (zero), results in an infeasible solution, so we remove it from further consideration.
If a warehouse must be built, then we need the additional constraint that x1 + x2 + x4 + x5 = 1. The implicit constraint for an SOS Type 1 is less than or equal to one. The linear programming relaxation may more closely resemble the MIP if we add that constraint.
