Engineering Optimization: Theory and Practice, Fourth Edition

608 Integer Programming

Method of Findingq 0 , q 1 , q 2 ,.... LetMbe the given positive integer. To find its

binary representationqnqn− 1... q 1 q 0 , we compute the following recursively:

b 0 =M (10.35)

b 1 =

b 0 −q 0

2

b 2 =

b 1 −q 1

2

..

.

bk=

bk− 1 −qk− 1

2

whereqk= if 1 bkis odd andqk= if 0 bkis even. The procedure terminates when

bk=. 0

Equation (10.33) guarantees thatxican take any feasible integer value less than

or equal toui. The use of Eq. (10.33) in the problem stated in Eq. (10.30) will convert

the integer programming problem into a binary one automatically. The only difference

is that the binary problem will haveN 1 +N 2 + · · · +Nnzero–one variables instead

of thenoriginal integer variables.

10.5.2 Conversion of a Zero–One Polynomial Programming Problem
into a Zero–One LP Problem

The conversion of a polynomial programming problem into a LP problem is based on

the fact that

x

aki

i ≡xi (10.36)

if xi is a binary variable (0 or 1) andakiis a positive exponent. Ifaki= , then 0

obviously the variablexiwill not be present in thekth term. The use of Eq. (10.36)

permits us to write thekth term of the polynomial, Eq. (10.31), as

ck

∏nk

l= 1

(xl)akl=ck

∏nk

l= 1

xl=ck(x 1 , x 2 ,... , xnk) (10.37)

Since each of the variablesx 1 , x 2 ,... can take a value of either 0 or 1, the product

(x 1 x 2 · · ·xnk) alsowill take a value of 0 or 1. Hence by defining a binary variable

ykas

yk=x 1 x 2 · · ·xnk=

∏nk

l= 1

xl (10.38)