Separable Programming

Separable programming is an approximate method for solving nonlinear problems.

It involves a minor modification of the simplex technique. This technique can be applied to problems in which all the nonlinear functions are separable. A separable function can be expressed as the sum of sub-functions where each sub-function is a function of one variable only.

"Sometimes it's better to break a single large problem into several small problems." -Vinay Chhabra & Manish Dewan

The main idea behind this technique is to construct a constrained optimization model that linearly approximates the original nonlinear problem. This technique has a considerable practical significance because after breaking the problem, usual simplex method with certain modifications can be applied. But this technique increases the computational burden because converting a nonlinear problem into an approximate version with separable functions increases the size of the model.

Many nonlinear expressions can be converted into separable form by introducing additional variables and definitional constraints.

General Form of Separable Programming Problem

Maximize f0 (x1, x2, ........, xn)

subject to

f1 (x1, x2, ........, xn) ≤ bi; i = 1, 2, ......, m
xj ≥ 0, j = 1, 2, ......, n

If the objective function and the constraints are separable, then we can write

f0 (x1, x2, ........, xn) = f0j (xj)

fi (x1, x2, ........, xn) = fij (xj)

i = 1, 2, ......, m

Thus, the problem under consideration can be expressed as

Maximize f0j (xj)

subject to

fij (xj) ≤ bi; i = 1, 2, ......, m

xj ≥ 0

Suppose there are two break points. We can evaluate fij (xj) at two consecutive break points and then make a linear approximation of fij (xj) between xj = ajk and xj = ajk + 1 in terms of two end points fij (ajk) and fij (ajk + 1) as:

fij (xj) = Wjk fij (ajk) + Wjk + 1fij (ajk + 1)

ajk ≤ xj ≤ ajk + 1

Wjk + Wjk + 1 = 1, Wjk ≥ 0

The Wjk values are weights assigned to the kth break point.

In general, there are kj break points for the sub-function rather than two. The function fij (xj) can be expressed as

fij (xj) = Wjk fij (ajk)

In the above expression, not more than two Wjk can be positive. And if two are positive, then they must be adjacent.

Wjk ≥ j = 1, 2, ......, n; k = 1, 2, ......, kj

Wjk = 1

Thus, the technique of separable programming transforms the original nonlinear programming problem into a linear programming problem with decision variables Wjk.

Share This Article