Nonlinear Programming

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.

The general form of a separable programming problem is given by

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

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

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.