Engineering Optimization: Theory and Practice, Fourth Edition

602 Integer Programming

which can be seen to be infeasible. Hence the constraint Eq. (10.26) is added at the

end of Table 10.2, and the dual simplex method applied. This procedure is repeated

the required number of times until the optimal mixed integer solution is found.

Discussion. In the derivation of the Gomory constraint, Eq. (10.26), we have not

made use of the fact that some of the variables(yj) ight be integer variables. Wem

notice that any integer value can be added to or subtracted from the coefficient of

aik(=a+ik+ai−k) f an integer variableo ykprovided that we subtract or add, respectively,

the same value toxiin Eq. (10.13), that is,

∑n

j= 1

j=k

aijyj+(aik± δ)yk=βi+bˆi− (xi∓ δ) (10.27)

From Eq. (10.27), the same logic as was used in the derivation of Eqs. (10.18) and

(10.24) can be used to obtain the same final equation, Eq. (10.26). Of course, the

coefficients of integer variablesyk will be altered by integer amounts in Eq. (10.26).

Ithas been established that to cut the feasible region as much as possible (through the

Gomory constraint), we have to make the coefficients of integer variablesykas small

as possible. We can see that the smallest positive coefficient we can have foryj in

Eq. (10.13) is

αij=aij− ˆaij

and the largest negative coefficient as

1 −αij= 1 −aij+ ˆaij

whereaˆijis the integer obtained by truncating the fractional part ofaijandαijis the

fractional part. Thus we have a choice of two expressions,(aij− ˆaij) nd (1a −aij+

aˆij) for the coefficients of, yjin Eq. (10.26). We choose the smaller one out of the

twoto make the Gomory constraint, Eq. (10.26), cut deeper into the original feasible

space. Thus Eq. (10.26) can be rewritten as

si=

∑

j

ai+jyj+

βi

βi− 1

∑

j

(+a−ij)yj

︸ ︷︷ ︸

for noninterger variablesyj

+

∑

j

(aij− ˆaij)yj

︸ ︷︷ ︸

for integer variablesyj

and foraij− ˆaij≤βi

+

βi

βi− 1

∑

j

( 1 −aij+ ˆaij)yj−

︸ ︷︷ ︸

for integer variablesyj

and foraij− ˆaij>βi

βi

where the slack variablesiis not restricted to be an integer.

Example 10.2 Solve the problem of Example 10.1 withx 2 only restricted to take

integer values.