Engineering Optimization: Theory and Practice, Fourth Edition

10.3 Gomory’s Cutting Plane Method 593

expressed, from theith equation of Table 10.2, as

xi=bi−

∑n

j= 1

aijyj (10.2)

wherebiis a noninteger. Let us write

bi=bˆi+βi (10.3)

aij= ˆaij+αij (10.4)

wherebˆiandaˆijdenote the integers obtained by truncating the fractional parts frombi
andaij, respectively. Thusβiwill be a strictly positive fraction (0<βi< ) and 1 αij
will be a nonnegative fraction (0≤αij< ). With the help of Eqs. (10.3) and (10.4), 1
Eq. (10.2) can be rewritten as

βi−

∑n

j= 1

αijyj=xi−bˆi+

∑n

j= 1

aˆijyj (10.5)

Since all the variablesxiandyjmust be integers at an optimal integer solution, the
right-handside of Eq. (10.5) must be an integer. Thus we obtain

βi−

∑n

j= 1

αijyj= ntegeri (10.6)

Notice thatαij are nonnegative fractions andyj are nonnegative integers. Hence the
quantity

∑n
j= 1 αijyjwill always be a nonnegative number. Sinceβiis a strictly positive
fraction, we have


βi−

∑n

j= 1

αijyj



≤βi< 1 (10.7)

As the quantity

(

βi−

∑n

j= 1 αijyj

)

has to be an integer [from Eq. (10.6)], it can be

either a zero or a negative integer. Hence we obtain the desired constraint as

+βi−

∑n

j= 1

αijyj≤ 0 (10.8)

By adding a nonnegative slack variablesi, the Gomory constraint equation becomes

si−

∑n

j= 1

αijyj= −βi (10.9)

wheresimust also be an integer by definition.