Using Special Ordered Sets

Using Special Ordered Sets

A special ordered set (SOS) is an additional way to specify integrality conditions in a model. There are various types of SOS:

SOS Type 1 is a set of variables (whether all integer, all continuous, or mixed integer and continuous) where at most one variable may be nonzero.
SOS Type 2 is a set or integer or continuous variables where at most two variables may be nonzero. If two variables are nonzero, they must be adjacent in the set.

ILOG CPLEX uses special branching strategies to take advantage of SOSs. The special branching strategies depend upon the order among the variables in the set. The order is specified by assigning weights to each variable. The order of the variables in the model (such as in the MPS or LP format data file, or the column index in a Callable Library application) is not used in SOS branching. If there is no order relationship among the variables (such that weights cannot be specified or would not be meaningful), SOS branching should not be used. For many classes of problems, these branching strategies can significantly improve performance.

Copyright © 2002 ILOG
http://www.ilog.com

Previous Page: Using Sensitivity Information in a MIP

Return to Top

Next Page: Example: SOS Type 1 for Sizing a Warehouse