[Help-glpk] Re: SOS2 constraints in GLPK

[Andrew Makhorin]

SOS2 (Special Ordered Set of Type 2) constraints are normally used to
model piecewise linear functions in (convex and non-convex) separable
programming.

In general case a SOS2 constraint is completely defined by specifying
a set of variables { t1, t2, ..., tn }; it is equivalent to the
following three constraints:

   t1, t2, ..., tn >= 0

   t1 + t2 + ... + tn = 1

   only one or two adjacent (i.e. t[i] and t[i+1]) can be non-zero

Let we need to model a piecewise linear function:

   y = f(x)

specified by its node points (x1,y1), (x2,y2), ..., (xn,yn).


   ^ y
   |                     (x3,y3)
   |                       *                           *
   |                   /        \                    / (xn,yn)
   |               /                 \             /
   |           *                          \      /
   |         / (x2,y2)                         *
   |       /                                  ...
   |     /
   |   *
   | (x1,y1)
   |
   +------------------------------------------------------> x

The standard description based on SOS2 constraint is the following:

   x = x1 * t1 + x2 * t2 + ... + xn * tn

   y = y1 * t1 + y2 * t2 + ... + yn * tn

   SOS2: { t1, t2, ..., tn }

where SOS2 variables t1, t2, ..., tn play the role of interpolation
parameters.

Implementation of SOS2 constraints in the simplex method assumes an
additional rule to choose a variable to enter the basis. Namely, if
t[i] is basic, only t[i-1] or t[i+1] can be basic, while other SOS2
variables have to be non-basic (therefore, fixed at zero).

However, since the set of feasible solutions may be non-convex, such
version of the simplex method allows obtaining only a local optimum.

SOS2 constraints are not implemented in GLPK, but a piece-wise linear
function can be easily modeled through binary variables as follows.

Let z1, z2, ..., z[n-1] be binary variables, where

   z[i] = 1 means that x[i] <= x <= x[i+1] and y[i] <= y <= y[i+1]

Then

   z[1] + z[2] + ... + z[n-1] = 1

   0 <= s[i] <= z[i]  for i = 1, 2, ..., n-1

   x = x1 * z1 + (x2 - x1) * s1 +
       x2 * z2 + (x3 - x2) * s2 +
       . . .
       x[i] * z[i] + (x[i+1] - x[i]) * s[i] +
       . . .
       x[n-1] * z[n-1] + (x[n] - x[n-1]) * s[n-1]

   y = y1 * z1 + (y2 - y1) * s1 +
       y2 * z2 + (y3 - y2) * s2 +
       . . .
       y[i] * z[i] + (y[i+1] - y[i]) * s[i] +
       . . .
       y[n-1] * z[n-1] + (y[n] - y[n-1]) * s[n-1]

The main advantage of this description is that the mip solver is always
able to find a global optimum.

If necessary, SOS2 constraints can be modeled independently on modeling
a piece-wise linear function as follows.

Let { t1, t2, ..., tn } be a SOS2 constraint. Then its equivalent
description is the following:

   z[1] + z[2] + ... + z[n-1] = 1

   0 <= s[i] <= z[i]  for i = 1, 2, ..., n-1

   t1 = z1 - s1
   t2 = z2 - s2 + s1
   . . .
   t[i] = z[i] - s[i] + s[i-1]
   . . .
   t[n-1] = z[n-1] - s[n-1] + s[n-2]
   t[n] = s[n-1]

where z[1], ..., z[n-1] are binary variables, and z[i] = 1 means that
only t[i] and t[i+1] are non-zero.


Andrew Makhorin