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.
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.
Maximize f0 (x1, x2, ........, xn)
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)
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.