Engineering Optimization: Theory and Practice, Fourth Edition

10.7 Sequential Linear Discrete Programming 617

subject to

gj(X)≈gj(X^0 )+

∑n^0

i= 1

∂gi

∂xi

(n 0

∑

l= 1

yildil−xi^0

)

+

∑n

i=n 0 + 1

∂gj

∂xi(xi−x

0

i)≤^0 ,

j= 1 , 2 ,... , m (10.67)

hk(X)≈hk(X^0 )+

∑n^0

i= 1

∂hk

∂xi

(n 0

∑

l= 1

yildil−xi^0

)

+

∑n

i=n 0 + 1

∂hk

∂xi(xi−x

0

i)=^0 ,

k= 1 , 2 ,... , p (10.68)

∑q

j= 1

yij= 1 , i= 1 , 2 ,... , n 0 (10.69)

yij= or 1 0 , i= 1 , 2 ,... , n 0 , j= 1 , 2 ,... , q (10.70)

xi(l)≤xi^0 +δxi≤x(u)i , i=n 0 + 1 ,n 0 + 2 ,... , n (10.71)

The problem stated in Eqs. (10.66) to (10.71) can now be solved as a mixed-integer
LP problem by treating bothyij (i= 1 , 2 ,... , n 0 , j = 1 , 2 ,... , q)andxi(i=n 0 + , 1
n 0 + 2 ,... , n)as unknowns.
In practical implementation, the initial linearization pointX^0 is to be selected
carefully.In many cases the solution of the discrete problem is expected to lie in
the vicinity of the continuous optimum. Hence the original problem can be solved as
a continuous nonlinear programming problem (by ignoring the discrete nature of the
variables) using any of the standard nonlinear programming techniques. If the resulting
continuous optimum solution happens to be a feasible discrete solution, it can be used as
X^0. Otherwise, the values ofxifrom the continuous optimum solution are rounded (in
adirection away from constraint violation) to obtain an initial feasible discrete solution
X^0. Once the first linearized discrete problem is solved, the subsequent linearizations
can be made using the result of the previous optimization problem.

Example 10.5 [10.26]

Minimizef (X)= 2 x 12 + 3 x 22

subject to

g(X)=

1

x 1

+

1

x 2

− 4 ≤ 0

x 1 ∈ { 0. 3 , 0. 7 , 0. 8 , 1. 2 , 1. 5 , 1. 8 }

x 2 ∈ { 0. 4 , 0. 8 , 1. 1 , 1. 4 , 1. 6 }

SOLUTION In this example, the set of discrete values of each variable is truncated
by allowing only three values—its current value, the adjacent higher value, and the