Engineering Optimization: Theory and Practice, Fourth Edition

10.3 Gomory’s Cutting Plane Method 601

Thus Eq. (10.13) yields

∑n

j= 1

(ai+j+a−ij)yj≤βi− 1 (10.21)

Since
∑n

j= 1

a−ijyj≤

∑n

j= 1

(a+ij+ai−j)yj

we obtain

∑n

j= 1

ai−jyj≤βi− 1 (10.22)

Upon dividing this inequality by the negative quantity (βi− ), we obtain 1

1

βi− 1

∑n

j= 1

a−ijyj≥ 1 (10.23)

Multiplying both sides of this inequality by βi> 0 , we can write the inequality
(10.23) as

βi

βi− 1

∑n

j= 1

a−ijyj≥βi (10.24)

Since one of the inequalities in (10.18) and (10.24) must be satisfied, the following
inequality must hold true:

∑n

j= 1

ai+jyj+

βi

βi− 1

∑n

j= 1

(a−ij)yj≥βi (10.25)

By introducing a slack variablesi, we obtain the desired Gomory constraint as

si=

∑n

j= 1

a+ijyj+

βi

βi− 1

∑n

j= 1

aijyj−βi (10.26)

This constraint must be satisfied before the variablexibecomes an integer. The slack
variablesiis not required to be an integer. At the optimal solution of the ordinary LP
problem (given by Table 10.2), allyj= and hence Eq. (10.26) becomes 0

si= −βi=negative