help-glpk
[Top][All Lists]

## [Help-glpk] Re: SOS2 constraints in GLPK

 From: Andrew Makhorin Subject: [Help-glpk] Re: SOS2 constraints in GLPK Date: Sat, 2 Jun 2007 12:44:28 +0400

```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

```