Engineering Optimization: Theory and Practice, Fourth Edition

620 Integer Programming

the point always remains in the feasible region. The termskQk(Xd) an be consideredc

as a penalty term withskplaying the role of a weighing factor (penalty parameter). Th e

functionQk(Xd) s constructed so as to give a penalty whenever some of the variablesi

inXdtake values other than integer values. Thus the functionQk(Xd) as the propertyh

that

Qk(Xd)=

{

0 if Xd∈Sd

μ > 0 if Xd∈/Sd

(10.75)

We can take, for example,

Qk(Xd)=

∑

xi∈Xd

{

4

(

xi−yi

zi−yi

)(

1 −

xi−yi

zi−yi

)}βk

(10.76)

whereyi≤xi,zi≥xi, andβk≥ is a constant. Here 1 yiandziare the two neighbor-

ing integer values for the valuexi. The functionQk(Xd) s a normalized, symmetrici

beta function integrand. The variation of each of the terms under summation sign in

Eq. (10.76) for different values ofβkis shown in Fig. 10.9. The value ofβkhas to be

greater than or equal to 1 if the functionQkis to be continuous in its first derivative

over the discretization or integer points.

The use of the penalty term defined by Eq. (10.76) makes it possible to change

the shape of theφkfunction by changingβk, while the amplitude can be controlled by

the weighting factorsk. Theφkfunction given in Eq. (10.73) is now minimized for a

sequence of values ofrkandsksuch that fork→∞, we obtain

Minφk( X,rk, sk) →Minf (X)

gj( X)≥ 0 , j= 1 , 2 ,... , m

Qk(Xd)→ 0

(10.77)

In most of the practical problems, one can obtain a reasonably good solution by carrying

out the minimization ofφkeven for 5 to 10 values ofk.The method is illustrated in

Fig. 10.10 in the case of a single-variable problem. It can be noticed from Fig. 10.10

that the shape of theφfunction (also called the response function) depends strongly

on the numerical values ofrk,sk, andβk.

1.0

1.0

0.5

0.5

(^0) )(
Ri = [ (^4) (xzi−yi
i−yi
xi−yi
)(^1 −zi−y )i]
xi−yi
zi−yi
bk= 1.0
bk= 2.0
bk= 4.0
bk= 6.0
bk= 8.0
bk
Figure 10.9 Contour of typical term in Eq. (10.62) [10.4].