Special Ordered Sets (SOS)

[FBumann]

Defining Special Ordered Sets SOS1 & SOS2

I would really like to see the option to define special ordered sets through linopy (of course only for compatible solvers)
Below is a quick overwview on what SOS are and why they would be a nice addition.
If I get some approval I might try to implement it myself. Has someone tried it before?

Special Ordered Sets (SOS)

Special Ordered Sets (SOS) are specialized mathematical structures used in mixed-integer programming to model certain types of constraints more efficiently. There are two main types:

Special Ordered Set Type 1 (SOS1)

A set of variables where at most one variable can be non-zero. This is useful for mutually exclusive choices.

Special Ordered Set Type 2 (SOS2)

A set of ordered variables where at most two consecutive variables can be non-zero, and those two must be adjacent in the ordering. This is frequently used to model piecewise linear functions.

Key Benefits

1. Computational Efficiency: Branch-and-bound algorithms can exploit the structure of SOS constraints to make more intelligent branching decisions, often leading to faster solution times compared to using standard binary variables.

2. Modeling Elegance: SOS constraints provide a more natural way to express certain types of problems, particularly piecewise linear approximations of nonlinear functions.

3. Solution Quality: For some problem types, formulations using SOS can lead to tighter LP relaxations, resulting in better bounds during the solution process.

4. Reduced Model Size: In some cases, using SOS constraints can lead to models with fewer variables or constraints than equivalent formulations using binary variables.

5. Specialized Solver Support: Most commercial solvers (like CPLEX, Gurobi) have specialized algorithms to handle SOS constraints efficiently.

SOS constraints are particularly valuable in applications like:

• Supply chain optimization with fixed costs
• Facility location problems
• Energy production scheduling
• Financial portfolio optimization
• Approximating nonlinear functions in various optimization contexts

[fneum]

I would second this feature request.

In PyPSA, this would facilitate the modelling of

• endogenous technological learning (i.e. higher cost for first capacities built)
• part-load efficiencies of components (i.e. lower efficiency for first units)
• multi-bids of generators (i.e. higher bids for first units)

Example for technological learning with SOS2

Zeyen et al. (2023) https://www.nature.com/articles/s41467-023-39397-2