Special Ordered Set¶
A mixed-integer optimization constraint that orders a declared variable list and restricts its nonzero support to at most one member (SOS1) or at most two adjacent members (SOS2), exposing disjunctive structure for solver enforcement, branching, or reformulation.
Core Idea¶
A special ordered set (SOS) is a constraint supplied to a mixed-integer optimizer as an ordered list of variables with a restriction on which members may be nonzero. In an SOS of type 1, at most one member may be nonzero. In an SOS of type 2, at most two members may be nonzero and, when two are nonzero, they must be adjacent in the declared order.
The word “set” is historical and slightly misleading: order is operational, especially for SOS2. Modeling APIs usually pair each variable with a weight that determines its position. These weights are ordering keys, not objective coefficients or required variable values. Unique weights prevent ambiguity about adjacency.
Scope of Application¶
SOS constraints belong to mixed-integer, discrete, and global mathematical optimization. SOS1 commonly expresses alternative selection, complementarity-like exclusivity, or membership in a finite menu. SOS2 commonly expresses adjacent-breakpoint interpolation and separable piecewise-linear or nonconvex functions.
The member variables may be binary, integer, or continuous, subject to solver-specific requirements. Some historical descriptions emphasize nonnegative SOS2 variables because convex-combination applications use them. Current solver documentation defines the support restriction more generally; the modeler must consult the selected solver for bound and API semantics.
Clarity¶
A practical recognition test asks:
- What variables are members of the declared constraint?
- What weights or positions establish their order, and are those positions unambiguous?
- Is the type SOS1 or SOS2?
- What nonzero patterns are permitted under that type?
- Are separate constraints needed to require selection, normalization, interpolation, or function value?
- How does the solver define numerical zero and handle reformulation?
- Does the declaration survive model export and import?
Manages Complexity¶
Many nonconvex choices are unions of simpler regions: choose one mode, activate one alternative, or interpolate on one of several adjacent segments. Writing every disjunction manually can require auxiliary binaries and big-M bounds whose strength and numerical behavior depend on formulation choices.
An SOS declaration compresses the repeated disjunction into a solver-recognized object. The solver can branch on subsets or intervals of the ordered list, propagate zeros, derive cuts, or choose an encoding.
Abstract Reasoning¶
Several deductions follow immediately. An SOS1 feasible support is a union of coordinate axes (plus their common origin) restricted by the rest of the model. An SOS2 feasible support is a union of subspaces generated by adjacent coordinate pairs. Both are generally nonconvex unions even when each individual region is polyhedral.
Knowledge Transfer¶
Within optimization, the identity transfers across facility choice, scheduling modes, complementarity conditions, piecewise-linear cost and response curves, gas supply, network design, and other disjunctive models. Variables and application equations change; ordered support remains.
SOS2 supplies a bridge between numerical approximation and discrete search. A continuous function is sampled at ordered breakpoints; convex weights reconstruct an input and output; adjacency ensures the solution uses one segment; mixed-integer machinery then searches the nonconvex union.
Relationships to Other Abstractions¶
Current abstraction Special Ordered Set Domain-specific
Parents (1) — more general patterns this builds on
-
Special Ordered Set is a kind of Constraint Prime
An SOS is a strict instance of Constraint.
Hierarchy path (1) — routes to 1 parentless root
- Special Ordered Set → Constraint
Neighborhood in Abstraction Space¶
Special Ordered Set sits in a sparse region of the domain-specific corpus (84th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (1565 abstractions)
Nearest neighbors
- Minimum Relevant Variables in a Linear System — 0.81
- Closed Preordered Set — 0.81
- Prime Graph — 0.80
- Ruzsa–Szemerédi Problem — 0.80
- NAND Logic — 0.80
Computed from structural-signature embeddings · 2026-09-08