SOS2

SOS2, short for Special Ordered Set of type 2, is a constraint used in mathematical optimization to model piecewise linear relationships within mixed-integer linear programming (MILP) formulations. It restricts a prescribed ordered set of candidate variables so that at most two can be nonzero, and if two are nonzero, they must be adjacent in the given order. This enforces that the solution lies on a single segment between two neighboring breakpoints, enabling accurate and compact piecewise linear approximations of nonlinear functions.

In practice, SOS2 constraints are applied to a sequence of weights or breakpoint variables that define a piecewise linear function. A common formulation uses weights lambda_i associated with breakpoints t_i. The constraints typically require that sum of the lambda_i equals 1, all lambda_i are nonnegative, and at most two adjacent lambda_i are nonzero. The decision variables of interest (for example, the interpolated x or the function value at x) are then expressed as convex combinations of the breakpoints and their function values. This yields a linear representation of many nonlinear relationships, suitable for MILP solvers.

SOS2 is widely implemented in optimization tools and solvers, including Gurobi, CPLEX, GLPK, and CBC, with solver-specific syntax. It is particularly useful for modeling piecewise linear costs, nonlinear mappings, and spline-like approximations while maintaining linearity in the core problem.

Compared with SOS1, which allows at most one nonzero variable, SOS2 permits two adjacent nonzeros, enabling smooth interpolation across segments. The concept is rooted in disjunctive programming and has become a standard modeling construct in optimization.