Example: SOS Type 1 for sizing a warehouse

To give you a feel for how SOSs can be useful, here’s an example of an SOS Type 1 used to choose the size of a warehouse. Assume for this example that a warehouse of 10000, 20000, 40000, or 50000 square feet can be built. Define binary variables for the four sizes, say, x1, x2, x4, and x5. 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. Then the weights of the set members are 10000, 20000, 40000, and 50000.
Assume furthermore that there is a known 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, the weighted average of the set is (0.1*10000 + 0.9*50000)/(0.1 + 0.9) = 46000.
Split the set before the variable with weight exceeding the weighted average. In this case, split the set like this: x1, x2, and x4 will be in one subset; x5 in the other.
Now 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 it is removed from further consideration.
If a warehouse must be built, then the additional constraint is needed that x1 + x2 + x4 + x5 = 1. The implicit constraint for an SOS Type 1 is less than or equal to one. The continuous relaxation may more closely resemble the MIP if that constraint is added.