Engineering Optimization: Theory and Practice, Fourth Edition

10.5 Integer Polynomial Programming 607

in two stages. In the first stage we see how an integer variable,xi, can be represented

by an equivalent system of zero–one (binary) variables. We consider the conversion

of a zero–one polynomial programming problem into a zero–one LP problem in the

second stage.

10.5.1 Representation of an Integer Variable by an Equivalent System
of Binary Variables
Letxibe any integer variable whose upper bound is given byuiso that

xi≤ui<∞ (10.32)

We assume that the value of the upper bounduican be determined from the constraints

of the given problem.

We know that in the decimal number system, an integerpis represented as

p=p 0 + 011 p 1 + 012 p 2 + · · ·, 0 ≤pi≤ 0 ( 1 − 1 = 9 )

for i= 0 , 1 , 2 ,...

and written asp= · · ·p 2 p 1 p 0 by neglecting the zeros to the left. For example, we write

the numberp=008076 as 8076 to representp= 6 +( 101 ) 7 +( 102 )( 0 )+( 103 ) 8 +

( 104 ) 0 +( 105 ). In a similar manner, the integer 0 pcan also be represented in binary

number system as

p=q 0 + 21 q 1 + 22 q 2 + 23 q 3 + · · ·

where 0≤qi≤( 2 − 1 = 1 )fori= 0 , 1 , 2 ,.. ..

In general, ifyi(^0 ), y(i^1 ), yi(^2 ),... denote binary numbers (which can take a value of

0 or 1), the variablexican be expressed as

xi=

∑Ni

k= 0

2 ky

(k)

i (10.33)

whereNiis the smallest integer such that

ui+ 1

2

≤ 2 Ni (10.34)

Thus the value ofNican be selected for any integer variablexionce its upper bound

uiis known. For example, for the number 97, we can takeui= 7 and hence the 9

relation

ui+ 1

2

=

98

2

= 49 ≤ 2 Ni

is satisfied forNi≥. Hence by taking 6 Ni= , we can represent 6 uias

97 =q 0 + 21 q 1 + 22 q 2 + 23 q 3 + 24 q 4 + 25 q 5 + 26 q 6

whereq 0 = , 1 q 1 =q 2 =q 3 =q 4 = , and 0 q 5 =q 6 =. A systematic method of find- 1

ing the values ofq 0 , q 1 , q 2 ,... is given below.