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.

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.

General Form of Separable Programming Problem

Maximize f₀ (x₁, x₂, ........, x_n)

subject to

f₁ (x₁, x₂, ........, x_n) ≤ b_i; i = 1, 2, ......, m
x_j ≥ 0, j = 1, 2, ......, n

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

f₀ (x₁, x₂, ........, x_n) = f_0j (x_j)

f_i (x₁, x₂, ........, x_n) = f_ij (x_j)

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

Thus, the problem under consideration can be expressed as

Maximize f_0j (x_j)

subject to

f_ij (x_j) ≤ b_i; i = 1, 2, ......, m

x_j ≥ 0

Suppose there are two break points. We can evaluate f_ij (x_j) at two consecutive break points and then make a linear approximation of f_ij (x_j) between x_j = a_j^k and x_j = a_j^{k + 1} in terms of two end points f_ij (a_j^k) and f_ij (a_j^{k + 1}) as:

f_ij (x_j) = W_j^k f_ij (a_j^k) + W_j^{k + 1}f_ij (a_j^{k + 1})

a_j^k ≤ x_j ≤ a_j^{k + 1}

W_j^k + W_j^{k + 1} = 1, W_j^k ≥ 0

In general, there are k_j break points for the sub-function rather than two. The function f_ij (x_j) can be expressed as

f_ij (x_j) = W_j^k f_ij (a_j^k)

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

W_j^k ≥ j = 1, 2, ......, n; k = 1, 2, ......, k_j

W_j^k = 1

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