Piecewise linear approximation SOS2

[Martine R]

I'm really interested in how the SOS2 formulation of Gurobi. I found an article that reviews some other piecewise linearization formulations (https://www.hindawi.com/journals/mpe/2013/101376/). Method 1 is the 'standard ' labda formulation and, if m is the amount of segments, uses m binary variables, m+1 continuous variables and m+5 constraints. While method 5 (Vielma & Nemhauser, 2011) uses log_2 m binary variables, m+1 continuous variables and 3+2*log_2 m constraints.This last method is supposed to be the fastest method, but compared to simply using the Gurobi function: model.addSOS(GRB.SOS_TYPE2) it is actually significantly slower. 

Any insights on how the SOS2 constraints in Gurobi work are greatly appreciated.

Thank you,

Martine 

[Tobias Achterberg]

The SOS2 constraints are just a tool that allows you to model piece-wise linear
constraints. By themselves, SOS2 constraints like

SOS2(x1,...,xn)

just state that at most two of the given variables can be non-zero, and if there are two
non-zero variables then these two need to be adjacent to each other in the list.

This enables the typical modeling of a piece-wise linear constraint. Assume you have
break-points (X1,Y1), ..., (Xn,Yn), then your model would look like this:


x = X1 * z1 + ... + Xn * zn
y = Y1 * z1 + ... + Yn * zn
z1 + ... + zn = 1
SOS2(z1,...,zn)
zj >= 0 for all j=1,...,n

The first two constraints define the x and y coordinates of your piece-wise linear
function. The third constraint says that (x,y) should be a convex combination of the
(Xj,Yj) points. Finally, the SOS2 constraint says, that (x,y) should actually be a convex
combination of two adjacent (Xj,Yj) points.

Internally, the SOS2 constraint is dealt with by branching: if the LP relaxation violates
an SOS2 constraint, i.e., there are two non-zero variables that are not adjacent to each
other, then you select some break point k in [2,...,n-1] so that there are non-zero
variables on each side of the split, and branch using the disjunction

(z1 = ... = zk-1 = 0) or (zk+1 = ... = zn = 0).


Hope this helps.


Tobias