19.2 Sos2 Constraint (sos-2)

Run LPL Code  ,  PDF Document)

A SOS2 (special order set of type 2) constraint is a set of variables where at most two adjacent variable in the set can take a value different from zero.

Given a set of variables xi with i I = {1,,n}. If the variables are real (or integer) then an additional binary variable yi has to be introduced together with the constraints (where upi is an upper bound on the variable xi) :

∑
   yi                                        ≤   2
 i
xi                                           ≤   upi ⋅ yi forall i ∈ I
yi + yj <= 1   forall i ∈ I,j ∈ {i + 2,...,n}

In LPL, we can use the function Sos2 to specify a SOS2 constraint. For example, to specify that only in a indexed list of variable must be non-zero, one specifies:

  constraint D: Sos2( {i} x[i] );

Listing 22: The Complete Model implemented in LPL [10]
model sos2 "Sos2 Constraint"; 
  set i:=1..10; 
  parameter up:=10.2; 
  variable x{i} [0..up]; 
  constraint A: Sos2({i} x); 
  maximize obj: sum{i} i*x; 
  Writep(obj,x); 
end

Note only Gurobi (and Cplex) understand this syntax from LPL, otherwise the explicit formulation must be used as follows:

  model sos2; 
    set i,j:=1..10; 
    parameter up:=10.2; 
    variable x{i} [0..up]; 
    binary y{i}; 
    constraint B: sum{i} y <= 2; 
    constraint C{i}: x <= up*y; 
    constraint D{i,j| j>=i+2}: y[i] + y[j] <= 1; 
    maximize obj: sum{i} i*x; 
    Writep(obj,x); 
  end