OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

We examine one special kind of heuristic algorithm (called *separable
programming*) that can be applied to certain types of nonlinear
program's. (A heuristic algorithm is an algorithm that does not guarantee
to find an optimal solution). We will illustrate separable programming
by applying it to an example.

Consider the following NLP (nonlinear program)

maximise (x_{1})² + x_{2 }subject to x_{1}+ x_{2}<= 7 x_{1}<= 5 x_{2}<= 3 x_{1},x_{2}>= 0

Here we have only one nonlinear term (x_{1})² which is
in the objective function which we are trying to maximise.

Consider the example NLP. Then the only nonlinear term is (x_{1})²
and this nonlinear term involves just the single variable x_{1}.
We can deduce from the NLP that this single variable x_{1} must
lie between zero and five (0 <= x_{1} <= 5). Hence (x_{1})²
- the nonlinear term - must lie between zero and 25 and so we have the
graph shown below.

Now one obvious way of solving (heuristically, that is approximately)
the NLP is to approximate the nonlinear term (x_{1})² by some
linear term since then we would then have an LP which we could solve to
give an approximate (heuristic) solution to the original NLP. To see how
this can be done choose some x_{1} values between 0 and 5 (e.g.
x_{1} = 2, x_{1} = 3) and for these (two) x_{1}
values define (three) straight lines to give a linear approximation of
(x_{1})² in the range (0 <= x_{1} <= 5) we are
interested in (as shown above).

Over the entire range 0 <= x_{1} <= 5 with the breakpoints
defined at x_{1} = 0, x_{1} = 2, x_{1} = 3 and
x_{1} = 5 (the two breakpoints we had before and the two endpoints)
we *claim *that introducing variables A_{1}, A_{2},
A_{3}, A_{4} (>= 0), 4 breakpoints in all so 4 variables,
one associated with each breakpoint, i.e.

- A
_{1}associated with the first breakpoint (at x_{1}= 0), - A
_{2}associated with the second breakpoint (at x_{1}= 2), - A
_{3}associated with the third breakpoint (at x_{1}= 3), - A
_{4}associated with the fourth breakpoint (at x_{1}= 5)

where

A_{1}+ A_{2}+ A_{3}+ A_{4}= 1 (1)

and

x_{1}= A_{1}(0) + A_{2}(2) + A_{3}(3) + A_{4}(5) (2)

and

either only one A_{i}(some i <= 4) non-zero (3)

or only two adjacent A_{i}, A_{i+1}(some i <= 3) non-zero (4)

enables us to approximate (x_{1})² by the *linear*
expression

A_{1}(0)² + A_{2}(2)² + A_{3}(3)²
+ A_{4}(5)²

To see whether this claim is valid consider a few examples:

- x
_{1}= 3

Then the appropriate A_{i} (i=1,2,3,4) values are clearly A_{1}
= A_{2} = A_{4} = 0 and A_{3} = 1 with the approximation
of (x_{1})² being given by

A_{1}(0)² + A_{2}(2)² + A_{3}(3)²
+ A_{4}(5)² = 0 + 0 + 1(3)² + 0 = 9

So in this case the approximation of (x_{1})² is exact.

Note here that the values of x_{1} and A_{i} (i=1,2,3,4)
satisfy equations (1) and (2) and also that equation (3) is satisfied (but
not equation (4)).

Note also that the A_{i} (i=1,2,3,4) values are *uniquely*
defined (i.e. given x_{1} there is only one set of A_{i}
values satisfying equations (1), (2), (3) and (4)).

- x
_{1}= 2.25

Then the appropriate A_{i} (i=1,2,3,4) values can be deduced
as follows (with the aid of the diagram above).

x_{1} = 2.25 lies between the second and third breakpoints so
that A_{2} > 0 and A_{3} > 0 (implying A_{1}
= A_{4} = 0). Also x_{1} = 2.25 lies 0.25 (A_{3})
of the way from the second breakpoint to the third breakpoint. Hence A_{3}
= 0.25, A_{2} = 1 - A_{3} = 0.75 and A_{1} = A_{4}
= 0.

Note that equations (1) and (2) are satisfied as is equation (4) (but not equation (3)).

The approximation of (x_{1})² is given by

A_{1}(0)² + A_{2}(2)² + A_{3}(3)²
+ A_{4}(5)² = 0 + 0.75(2)² + 0.25(3)² + 0 = 5.25

Since x_{1} = 2.25 we have (x_{1})² = 5.0625 and
so we have a reasonable approximation.

- x
_{1}= 1.0

Then the appropriate A_{i} (i=1,2,3,4) values can be deduced
as follows. x_{1} = 1.0 lies between the first and second breakpoints
so that A_{1} >= 0 and A_{2} >= 0 (implying A_{3}
= A_{4} = 0). Also x_{1} = 1.0 lies 0.5 (A_{2})
of the way from the first breakpoint to the second breakpoint. Hence A_{2}
= 0.5, A_{1} = 1 - A_{2} = 0.5 and A_{3} = A_{4}
= 0.

Note again that equations (1) and (2) are satisfied as is equation (4) but not equation (3)).

The approximation of (x_{1})² is given by

A_{1}(0)² + A_{2}(2)² + A_{3}(3)²
+ A_{4}(5)² = 0 + 0.5(2)² + 0 + 0 = 2

Since x_{1} = 1.0 we have (x_{1})² = 1.0 so in
this case the approximation is not very near to the true value. Plainly
over the entire range for x_{1} (0 <= x_{1} <= 5)
the approximation will be better at some points than at others.

Note here that it is important to ensure that the A_{i} (i=1,2,3,4)
are such that *either* equation (3) *or* equation (4) is satisfied.
If this is not the case then the approximation will be very far from the
true value e.g. consider A_{1} = 0.55, A_{2} = A_{3}
= 0 and A_{4} = 0.45 which do not satisfy either equation (3) or
equation (4) but do satisfy equation (1) and equation (2) (with x_{1}
= 2.25). Then with these A_{i} values (i=1,2,3,4) the approximation
of (x_{1})² is given by

A_{1}(0)² + A_{2}(2)² + A_{3}(3)²
+ A_{4}(5)² = 0 + 0 + 0 + 0.45(5)² = 11.25

and compare this with the true value of 5.0625 and the previous approximation
of 5.25 which we obtained with A_{1} = 0, A_{2} = 0.75,
A_{3} = 0.25 and A_{4} = 0.

Hence we have shown how a nonlinear term like (x_{1})²
can be replaced by a linear approximation. So consider the original NLP
which we were trying to solve:

maximise (x_{1})² + x_{2}subject to x_{1}+ x_{2}<= 7 x_{1}<= 5 x_{2}<= 3 x_{1},x_{2}>= 0

Introducing the linear approximation for (x_{1})² we get
the LP:

maximise [A_{1}(0)² + A_{2}(2)² + A_{3}(3)² + A_{4}(5)²] + x_{2}subject to x_{1}+ x_{2}<= 7 x_{1}<= 5 x_{2}<= 3 x_{1}= A_{1}(0) + A_{2}(2) + A_{3}(3) + A_{4}(5) A_{1}+ A_{2}+ A_{3}+ A_{4}= 1 and either only one A_{i}(some i <= 4) non-zero or only two adjacent A_{i}, A_{i+1}(some i <= 3) non-zero x_{1},x_{2}>=0 and A_{i}>=0 i=1,2,3,4

This linear program is known as a *linear approximation* of the
original NLP and can be solved *heuristically* by a variant of the
simplex algorithm for LP.

Note here that we cannot solve this program optimally because of the
either/or restriction relating to the A_{i}'s. Whilst we could
resort to mixed-integer programming to deal with these either/or restrictions
this is seldom done, given the computational cost of solving an MIP optimally
and given that we are *approximating* the original NLP by the MIP.

Note also that other linear approximations exist - for example we could
have split the (x_{1})² nonlinear term differently by defining
more breakpoints. This would lead to a more accurate linear approximation
of (x_{1})² but at the expense of a larger program (more variables
and more constraints) for the variant of the simplex algorithm to solve
(i.e. we are trading off accuracy of approximation against computer time).

In fact it is usual to vary the spacing of the breakpoints so that we have more breakpoints in areas of the nonlinear function we think are of special interest (e.g. an area likely to be involved in the solution or an area where the value of the nonlinear function changes rapidly/significantly) and less breakpoints in other areas.

So far we have only considered nonlinear terms in the objective function but it is plain that we can also deal with nonlinear terms in the constraints in a similar manner to that used above.

Note here that the condition for us to be able to take any NLP and convert
it into a new, linear, program is that *each* nonlinear term is a
function of just a *single* variable and does not involve more than
one variable (i.e. the NLP contains terms like (x_{1})² and
(x_{2})³ but no terms like (x_{1})²(x_{2})^{5}
which involve two variables).

Summary

Let us then summarise the steps we need to go through to generate a linear approximation of an NLP:

Step 1

- ensure that each nonlinear term is just a function of a single variable

Step 2

- for each nonlinear term establish a range for the variable used in
the nonlinear term (e.g. in our example above the nonlinear term was (x
_{1})² and the range for x_{1}was 0 <= x_{1}<= 5)

Step 3

- introduce (arbitrary) breakpoints in the range of each variable, for
each nonlinear term (e.g. in our example above we had one nonlinear term
involving x
_{1}and breakpoints at x_{1}=2 and x_{1}=3 (plus the endpoints of x_{1}=0 and x_{1}=5))

Step 4

- for each nonlinear term construct the linear approximation in the same
manner as given in our example. To clarify the construction of the linear
approximation let f(x) be the nonlinear function we are approximating with
A
_{i}(i=1,...,n) the variables associated with the breakpoints p_{i}(i=1,...,n) then f(x) is approximated by the linear expression - A
_{1}(f(p_{1})) + A_{2}(f(p_{2})) + ... + A_{n}(f(p_{n})) - where x = A
_{1}(p_{1}) + A_{2}(p_{2}) + ... + A_{n}(p_{n}) - A
_{1}+ A_{2}+ ... + A_{n}= 1 - and either only one A
_{i}(some i <= n) non-zero or only two adjacent A_{i}, A_{i+1}(some i <= n-1) non-zero.

Step 5

- write out in full the complete linear approximation of the original NLP.

Any NLP in which all the nonlinear terms are just functions of single
variables is called a *separable program* and the above method of
linear approximation is sometimes called *separable programming*.

This restriction on the nature of nonlinear terms would seem to limit
the applicability of the method but in fact we can deal with some product
terms, like x_{1}x_{2}, by using the fact that

- x
_{1}x_{2}= [(x_{1}+ x_{2})/2]^{2}- [(x_{1}- x_{2})/2]^{2}

Again we shall illustrate by an example.

maximise 2x_{1}+ x_{2}subject to x_{1}x_{2}<= 10 x_{1}<= 5 x_{2}<= 3 x_{1},x_{2}>= 0

We approach the problem via the five steps given above.

- Step 1

we need first to remove the x_{1}x_{2} term (which is
a function of two variables). Substituting from above for x_{1}x_{2}
the nonlinear constraint

x_{1}x_{2} <= 10

becomes

[(x_{1} + x_{2})/2]^{2} - [(x_{1} -
x_{2})/2]^{2} <= 10

We now introduce two new variables y_{1} and y_{2} where
y_{1} = (x_{1} + x_{2})/2 and y_{2} = (x_{1}
- x_{2})/2

Note here that y_{1} >= 0 but y_{2} can be positive
or negative.

Then our nonlinear constraint becomes (y_{1})² - (y_{2})²
<= 10 which is in a form we can deal with (e.g. consider the example
given above where we approximated a square term).

- Step 2

establish a range for both y_{1} and y_{2}. To establish
a valid range for y_{1} we use the definition of y_{1}
given above. Since y_{1} = (x_{1} + x_{2})/2 it
is clear that

max value of y_{1} = ([max value of x_{1}] + [max value
of x_{2}])/2

and

min value of y_{1} = ([min value of x_{1}] + [min value
of x_{2}])/2

Now from the original NLP valid ranges for x_{1} and x_{2}
are 0 <= x_{1} <= 5 and 0 <= x_{2} <= 3

Hence

max value of y_{1} = (5 + 3)/2 = 4

min value of y_{1} = (0 + 0)/2 = 0

so that a valid range for y_{1} is 0 <= y_{1} <=
4.

To establish a valid range for y_{2} we proceed in a similar
manner. Since y_{2} = (x_{1} - x_{2})/2 it is clear
that

max value of y_{2} = ([max value of x_{1}] - [min value
of x_{2}])/2 and

min value of y_{2} = ([min value of x_{1}] - [max value
of x_{2}])/2

So again using 0 <= x_{1} <= 5 and 0 <= x_{2}
<= 3 we get that

max value of y_{2} = (5 - 0)/2 = 2.5

min value of y_{2} = (0 - 3)/2 = -1.5

Hence a valid range for y_{2} is -1.5 <= y_{2} <=
2.5.

- Step 3

introduce (arbitrary) breakpoints in the range of each variable, for each nonlinear term, as below:

Term Breakpoints Variables (y_{1})² y_{1}= 2, y_{1}= 3 A_{i}(i=1,2,3,4) (y_{2})² y_{2}= -1, y_{2}= 0, y_{2}= 2 B_{i}(i=1,2,3,4,5)

- Step 4

construct the linear approximation for each nonlinear term. Hence we
have (y_{1})² approximated by the linear expression

A_{1}(0)² + A_{2}(2)² + A_{3}(3)²
+ A_{4}(4)²

where

y_{1} = A_{1}(0) + A_{2}(2) + A_{3}(3)
+ A_{4}(4)

A_{1} + A_{2} + A_{3} + A_{4} = 1

and either only one A_{i} (some i <= 4) non-zero or only
two adjacent A_{i}, A_{i+1} (some i <= 3) non-zero

(y_{2})² approximated by the linear expression

B_{1}(-1.5)² + B_{2}(-1)² + B_{3}(0)²
+ B_{4}(2)² + B_{5}(2.5)²

where

y_{2} = B_{1}(-1.5) + B_{2}(-1) + B_{3}(0)
+ B_{4}(2) + B_{5}(2.5)

B_{1} + B_{2} + B_{3} + B_{4} + B_{5}
= 1

and either only one B_{i} (some i <= 5) non-zero or only
two adjacent B_{i}, B_{i+1} (some i <= 4) non-zero

- Step 5

the complete linear approximation of the original NLP is therefore given by:

maximise 2x_{1}+ x_{2}subject to y_{1}= (x_{1}+ x_{2})/2 y_{2}= (x_{1}- x_{2})/2 y_{1}= A_{1}(0) + A_{2}(2) + A_{3}(3) + A_{4}(4) y_{2}= B_{1}(-1.5) + B_{2}(-1) + B_{3}(0) + B_{4}(2) + B_{5}(2.5) A_{1}+ A_{2}+ A_{3}+ A_{4}= 1 B_{1}+ B_{2}+ B_{3}+ B_{4}+ B_{5}= 1 [A_{1}(0)² + A_{2}(2)² + A_{3}(3)² + A_{4}(4)²] - [B_{1}(-1.5)² + B_{2}(-1)² + B_{3}(0)² + B_{4}(2)² + B_{5}(2.5)²] <= 10 x_{1}<= 5 x_{2}<= 3 x_{1}, x_{2}, y_{1}>= 0 y_{2}can be positive or negative A_{i}>= 0 i=1,2,3,4 B_{i}>= 0 i=1,2,3,4,5 and either only one A_{i}(some i <= 4) non-zero or only two adjacent A_{i}, A_{i+1}(some i <= 3) non-zero and either only one B_{i}(some i <= 5) non-zero or only two adjacent B_{i}, B_{i+1}(some i <= 4) non-zero

Note here that the y variables can be eliminated from the above program
and so do not need to be explicitly considered.

Convert the following NLP into an appropriate linear approximation. Discuss the trade-off that occurs between the size of the resulting linear program and the accuracy of the approximation.

maximise (x_{1})^{5}+ x_{2}subject to x_{1}x_{2}<= 17 x_{1}<= 3 x_{2}<= 4 x_{1},x_{2}>= 0

We again approach the problem via the five steps given above.

- Step 1

in this NLP we have two nonlinear terms (x_{1})^{5}
and x_{1}x_{2}. Both of these nonlinear terms are functions
of single variables if we use the expansion of x_{1}x_{2}
that we gave above, namely:

x_{1}x_{2} = [(x_{1} + x_{2})/2]^{2}
- [(x_{1} - x_{2})/2]^{2}

By putting

y_{1} = (x_{1} + x_{2})/2

and y_{2} = (x_{1} - x_{2})/2

where y_{1} >= 0 but y_{2} can be positive or negative
we have that the nonlinear constraint

x_{1}x_{2} <= 17

becomes (y_{1})² - (y_{2})² <= 17

which is in a form we can deal with as it contains two nonlinear terms, each a function of a single variable.

- Step 2

establish a valid range for each of the variables involved in a nonlinear
term. We have three nonlinear terms (x_{1})^{5}, (y_{1})²
and (y_{2})² so we need to establish a valid range for x_{1},
y_{1} and y_{2}.

Looking back at the original NLP it is clear that a valid range for
x_{1} is given by 0 <= x_{1} <= 3.

To establish a valid range for y_{1} we use the definition of
y_{1} given above.

Since y_{1} = (x_{1} + x_{2})/2 it is clear
that

max value of y_{1} = ([max value of x_{1}] + [max value
of x_{2}])/2 and

min value of y_{1} = ([min value of x_{1}] + [min value
of x_{2}])/2

Now from the original NLP valid ranges for x_{1} and x_{2}
are given by 0 <= x_{1} <= 3 and 0 <= x_{2} <=
4 so that

max value of y_{1} = (3 + 4)/2 = 7/2

min value of y_{1} = (0 + 0)/2 = 0

Hence a valid range for y_{1} is 0 <= y_{1} <=
7/2.

We can establish a valid range for y_{2} in a similar manner.

Since y_{2} = (x_{1} - x_{2})/2 it is clear
that

max value of y_{2} = ([max value of x_{1}] - [min value
of x_{2}])/2 and

min value of y_{2} = ([min value of x_{1}] - [max value
of x_{2}])/2

and again using 0 <= x_{1} <= 3 and 0 <= x_{2}
<= 4

we get that

max value of y_{2} = (3 - 0)/2 = 3/2

min value of y_{2} = (0 - 4)/2 = -2

Hence a valid range for y_{2} is -2 <= y_{2} <=
3/2.

- Step 3

introduce (arbitrary) breakpoints in the range of each variable, for each nonlinear term, as below:

Term Breakpoints Variables (x_{1})^{5}x_{1}= 1, x_{1}= 2 A_{i}(i=1,2,3,4) (y_{1})² y_{1}= 1, y_{1}= 2 B_{i}(i=1,2,3,4) (y_{2})² y_{2}= -1, y_{2}= 0, y_{2}= 1 C_{i}(i=1,2,3,4,5)

- Step 4

construct the linear approximation for each nonlinear term. Hence we
have (x_{1})^{5} approximated by the linear expression

A_{1}(0)^{5} + A_{2}(1)^{5} + A_{3}(2)^{5}
+ A_{4}(3)^{5}

where

x_{1} = A_{1}(0) + A_{2}(1) + A_{3}(2)
+ A_{4}(3)

A_{1} + A_{2} + A_{3} + A_{4} = 1

and either only one A_{i} (some i <= 4) non-zero or only
two adjacent A_{i}, A_{i+1} (some i <= 3) non-zero

(y_{1})² approximated by the linear expression

B_{1}(0)² + B_{2}(1)² + B_{3}(2)²
+ B_{4}(7/2)²

where

y_{1} = B_{1}(0) + B_{2}(1) + B_{3}(2)
+ B_{4}(7/2)

B_{1} + B_{2} + B_{3} + B_{4} = 1

and either only one B_{i} (some i <= 4) non-zero or only
two adjacent B_{i}, B_{i+1} (some i <= 3) non-zero

(y_{2})² approximated by the linear expression

C_{1}(-2)² + C_{2}(-1)² + C_{3}(0)²
+ C_{4}(1)² + C_{5}(3/2)²

where

y_{2} = C_{1}(-2) + C_{2}(-1) + C_{3}(0)
+ C_{4}(1) + C_{5}(3/2)

C_{1} + C_{2} + C_{3} + C_{4} + C_{5}
= 1

and either only one C_{i} (some i <= 5) non-zero or only
two adjacent C_{i}, C_{i+1} (some i <= 4) non-zero

- Step 5

the complete linear programming approximation of the original NLP is therefore given by

maximise [A_{1}(0)^{5}+ A_{2}(1)^{5}+ A_{3}(2)^{5}+A_{4}(3)^{5}] + x_{2}subject to x_{1}= A_{1}(0) + A_{2}(1) + A_{3}(2) + A_{4}(3) y_{1 }= (x_{1}+ x_{2})/2 y_{2}= (x_{1}- x_{2})/2 y_{1}= B_{1}(0) + B_{2}(1) + B_{3}(2) + B_{4}(7/2) y_{2}=C_{1}(-2) + C_{2}(-1) + C_{3}(0) + C_{4}(1) + C_{5}(3/2) A_{1}+ A_{2}+ A_{3}+ A_{4}= 1 B_{1}+ B_{2}+ B_{3}+ B_{4}= 1 C_{1}+ C_{2}+ C_{3}+ C_{4}+ C_{5}= 1 [B_{1}(0)² + B_{2}(1)² + B_{3}(2)² + B_{4}(7/2)²] - [C_{1}(-2)² + C_{2}(-1)² + C_{3}(0)² + C_{4}(1)² + C_{5}(3/2)²] <= 17 x_{1}<= 3 x_{2}<= 4 All variables except y_{2}>= 0, y_{2}can be positive or negative and either only one A_{i}(some i <= 4) non-zero or only two adjacent A_{i}, A_{i+1}(some i <= 3) non-zero and either only one B_{i}(some i <= 4) non-zero or only two adjacent B_{i}, B_{i+1}(some i <= 3) non-zero and either only one C_{i}(some i <= 5) non-zero or only two adjacent C_{i}, C_{i+1}(some i <= 4) non-zero

Note here that the y variables (y_{1},y_{2}) can be
eliminated from the above program and do not need to be explicitly considered.

The trade-off between the size of the linear program and the accuracy
of the approximation occurs because the more breakpoints we introduce for
any nonlinear term the better we approximate the nonlinear term, but the
larger the resulting linear program.

Convert the following NLP into an appropriate linear approximation.

maximise (x_{1})² + 2x_{2}+ 3x_{3}subject to x_{2}+ log_{e}(x_{1}) >= 2 x_{2}x_{3}<= 20 2 <= x_{1}<= 3 x_{2}<= 5 x_{3}<= 20 x_{1},x_{2},x_{3}>= 0

We again approach the problem via the five steps given above.

- Step 1

in this NLP we have three nonlinear terms (x_{1})², log_{e}(x_{1})
and x_{2}x_{3}. All of these nonlinear terms are functions
of single variables if we use the expansion of x_{2}x_{3}
that we gave before, namely:

x_{2}x_{3} = [(x_{2} + x_{3})/2]^{2}
- [(x_{2} - x_{3})/2]^{2}

and putting

y_{1} = (x_{2} + x_{3})/2

y_{2} = (x_{2} - x_{3})/2

where y_{1} >= 0 but y_{2} could be positive or negative
we have that the nonlinear constraint

x_{2}x_{3} <= 20

becomes (y_{1})² - (y_{2})² <= 20

which is in a form we can deal with (as it contains two nonlinear terms, each a function of a single variable).

- Step 2

establish a valid range for each of the variables involved in a nonlinear term - these ranges are

Term Variable Range (x_{1}² x_{1}2 <= x_{1}<= 3 log_{e}(x_{1}) x_{1}2 <= x_{1}<= 3 (y_{1})² y_{1}0 <= y_{1}<= 25/2 (y_{2})² y_{2}-10 <= y_{2}<= 5/2

- Step 3

introduce (arbitrary) breakpoints in the range of each variable, for each nonlinear term as below:

Term Breakpoints Variables (x_{1})² None A_{i}(i=1,2) log_{e}(x_{1}) x_{1}= 2.5 B_{i}(i=1,2,3) (y_{1})² y_{1}= 4, y_{1}= 8 C_{i}(i=1,2,3,4) (y_{2})² y_{2}= -2, y_{2}= 0, y_{2}= 1 D_{i}(i=1,2,3,4,5)

Note here that we have different variables defined for the two nonlinear
terms that involve x_{1}. This is essential if (as above) we have
chosen different breakpoints for the two nonlinear terms. If we have the
same breakpoints then the variables should be the same.

- Step 4

construct the linear approximation for each nonlinear term. Hence we
have (x_{1})² approximated by the linear expression

A_{1}(2)² + A_{2}(3)²

where

x_{1} = A_{1}(2) + A_{2}(3)

A_{1} + A_{2} = 1

log_{e}(x_{1}) approximated by the linear expression

B_{1}(log_{e}(2)) + B_{2}(log_{e}(2.5))
+ B_{3}(log_{e}(3))

where

x_{1} = B_{1}(2) + B_{2}(2.5) + B_{3}(3)

B_{1} + B_{2} + B_{3} = 1

and either only one B_{i} (some i <= 3) non-zero or only
two adjacent B_{i}, B_{i+1} (some i <= 2) non-zero

Note especially here how the log_{e}(x_{1}) term has
been approximated.

(y_{1})² approximated by the linear expression

C_{1}(0)² + C_{2}(4)² + C_{3}(8)²
+ C_{4}(25/2)²

where

y_{1} = C_{1}(0) + C_{2}(4) + C_{3}(8)
+ C_{4}(25/2)

C_{1} + C_{2} + C_{3} + C_{4} = 1

and either only one C_{i} (some i <= 4) non-zero or only
two adjacent C_{i}, C_{i+1} (some i <= 3) non-zero

(y_{2})² approximated by the linear expression

D_{1}(-10)² + D_{2}(-2)² + D_{3}(0)²
+ D_{4}(1)² + D_{5}(5/2)²

where

y_{2} = D_{1}(-10) + D_{2}(-2) + D_{3}(0)
+ D_{4}(1) + D_{5}(5/2)

D_{1} + D_{2} + D_{3} + D_{4} + D_{5}
= 1

and either only one D_{i} (some i <= 5) non-zero or only
two adjacent D_{i}, D_{i+1} (some i <= 4) non-zero

- Step 5

the complete linear programming approximation of the original NLP is therefore given by

maximise [A_{1}(2)² + A_{2}(3)²] + 2x_{2}+ 3x_{3}subject to x_{1}= A_{1}(2) + A_{2}(3) x_{1}= B_{1}(2) + B_{2}(2.5) + B_{3}(3) y_{1}= (x_{2}+ x_{3})/2 y_{2}= (x_{2}- x_{3})/2 y_{1}= C_{1}(0) + C_{2}(4) + C_{3}(8)+ C_{4}(25/2) y_{2}= D_{1}(-10) + D_{2}(-2) + D_{3}(0) + D_{4}(1) + D_{5}(5/2) A_{1}+ A_{2}= 1 B_{1}+ B_{2}+ B_{3}= 1 C_{1}+ C_{2}+ C_{3}+ C_{4}= 1 D_{1}+ D_{2}+ D_{3}+ D_{4}+ D_{5}= 1 x_{2}+ [B_{1}(log_{e}(2)) + B_{2}(log_{e}(2.5)) + B_{3}(log_{e}(3))] >= 2 [C_{1}(0)² + C_{2}(4)² + C_{3}(8)² + C_{4}(25/2)²] - [D_{1}(-10)² + D_{2}(-2)² + D_{3}(0)² + D_{4}(1)² + D_{5}(5/2)²] <= 20 2 <= x_{1}<= 3 x_{2}<= 5 x_{3}<= 20 All variables except y_{2}>= 0, y_{2}can be positive or negative and either only one B_{i}(some i <= 3) non-zero or only two adjacent B_{i}, B_{i+1}(some i <= 2) non-zero and either only one C_{i}(some i <= 4) non-zero or only two adjacent C_{i}, C_{i+1}(some i <= 3) non-zero and either only one D_{i}(some i <= 5) non-zero or only two adjacent D_{i}, D_{i+1}(some i <= 4) non-zero

Note here that we have no either/or condition relating to A_{i}
since as we have only A_{1} and A_{2} the either/or condition
that we would normally include is automatically satisfied. Note also that
the y variables (y_{1},y_{2}) can be eliminated from the
above program and so do not need to be explicitly considered.

Transform the nonlinear program shown below to a linear program.

maximise (x_{1})³ + x_{1}+ x_{3}subject to x_{3}+ log_{e}(x_{1}) <= 7 x_{1}+ x_{2}+ x_{3}<= 9 5 <= x_{1}<= 10 0 <= x_{2}<= 7 4 <= x_{3}<= 15

- Step 1

each nonlinear term is already a function of a single variable.

- Step 2

the ranges are

Nonlinear term Variable Range (x_{1})³ x_{1}5 <= x_{1}<= 10 log_{e}(x_{1}) x_{1}5 <= x_{1}<= 10

- Step 3

we now introduce (arbitrary) breakpoints in the range of each variable, for each nonlinear term, as below

Term Breakpoints Variables (x_{1})³ x_{1}= 7 A_{i}(i=1,2,3) log_{e}(x_{1}) x_{1}= 6, x_{1}= 8 B_{i}(i=1,2,3,4)

Note here that although both nonlinear terms are functions of the same
variable (x_{1}) we have different breakpoints and hence different
variables (A_{i} and B_{i}).

- Step 4

Construct the linear approximation for each nonlinear term.

Hence we have (x_{1})³ approximated by the linear expression

A_{1}(5)³ + A_{2}(7)³ + A_{3}(10)³

where

x_{1} = A_{1}(5) + A_{2}(7) + A_{3}(10)

A_{1} + A_{2} + A_{3} = 1

and either only one A_{i} (some i <= 3) non-zero or only
two adjacent A_{i}, A_{i+1} (some i <= 2) non-zero

log_{e}(x_{1}) approximated by the linear expression

B_{1}(log_{e}(5)) + B_{2}(log_{e}(6))
+ B_{3}(log_{e}(8)) + B_{4}(log_{e}(10))

where

x_{1} = B_{1}(5) + B_{2}(6) + B_{3}(8)
+ B_{4}(10)

B_{1} + B_{2} + B_{3} + B_{4} = 1

and either only one B_{i} (some i <= 4) non-zero or only
two adjacent B_{i}, B_{i+1} (some i <= 3) non-zero

- Step 5

the complete linear approximation of the original NLP is therefore given by

maximise A_{1}(5)³ + A_{2}(7)³ + A_{3}(10)³ + x_{1 }+ x_{3}subject to x_{3}+ B_{1}(log_{e}(5)) + B_{2}(log_{e}(6)) + B_{3}(log_{e}(8)) + B_{4}(log_{e}(10)) <= 7 x_{1}= A_{1}(5) + A_{2}(7) + A_{3}(10) x_{1}= B_{1}(5) + B_{2}(6) + B_{3}(8) + B_{4}(10) A_{1}+ A_{2}+ A_{3}= 1 B_{1}+ B_{2}+ B_{3}+ B_{4}= 1 x_{1}+ x_{2}+ x_{3}<= 9 5 <= x_{1}<= 10 0 <= x_{2}<= 7 4 <= x_{3}<= 15 all variables >= 0 and either only one A_{i}(some i <= 3) non-zero or only two adjacent A_{i}, A_{i+1}(some i <= 2) non-zero and either only one B_{i}(some i <= 4) non-zero or only two adjacent B_{i}, B_{i+1}(some i <= 3) non-zero