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.