[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Helpglpk] Re: SOS2 constraints in GLPK
From: 
Andrew Makhorin 
Subject: 
[Helpglpk] 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 nonconvex) 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 nonzero
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[i1] or t[i+1] can be basic, while other SOS2
variables have to be nonbasic (therefore, fixed at zero).
However, since the set of feasible solutions may be nonconvex, such
version of the simplex method allows obtaining only a local optimum.
SOS2 constraints are not implemented in GLPK, but a piecewise linear
function can be easily modeled through binary variables as follows.
Let z1, z2, ..., z[n1] 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[n1] = 1
0 <= s[i] <= z[i] for i = 1, 2, ..., n1
x = x1 * z1 + (x2  x1) * s1 +
x2 * z2 + (x3  x2) * s2 +
. . .
x[i] * z[i] + (x[i+1]  x[i]) * s[i] +
. . .
x[n1] * z[n1] + (x[n]  x[n1]) * s[n1]
y = y1 * z1 + (y2  y1) * s1 +
y2 * z2 + (y3  y2) * s2 +
. . .
y[i] * z[i] + (y[i+1]  y[i]) * s[i] +
. . .
y[n1] * z[n1] + (y[n]  y[n1]) * s[n1]
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 piecewise linear function as follows.
Let { t1, t2, ..., tn } be a SOS2 constraint. Then its equivalent
description is the following:
z[1] + z[2] + ... + z[n1] = 1
0 <= s[i] <= z[i] for i = 1, 2, ..., n1
t1 = z1  s1
t2 = z2  s2 + s1
. . .
t[i] = z[i]  s[i] + s[i1]
. . .
t[n1] = z[n1]  s[n1] + s[n2]
t[n] = s[n1]
where z[1], ..., z[n1] are binary variables, and z[i] = 1 means that
only t[i] and t[i+1] are nonzero.
Andrew Makhorin
[Prev in Thread] 
Current Thread 
[Next in Thread] 
 [Helpglpk] Re: SOS2 constraints in GLPK,
Andrew Makhorin <=