Engineering Optimization: Theory and Practice, Fourth Edition

592 Integer Programming

adding these additional constraints is to reduce the original feasible convex region

ABCDto a new feasible convex region (such asABEFGD) such that an extreme

point of the new feasible region becomes an integer optimal solution to the integer

programming problem. There are two main considerations to be taken while select-

ing the additional constraints: (1) the new feasible region should also be a convex

set, and (2) the part of the original feasible region that is sliced off because of the

additional constraints should not include any feasible integer solutions of the original

problem.

In Fig. 10.3, the inclusion of the two arbitrarily selected additional constraintsPQ

andP′Q′gives the extreme pointF(x 1 = , 5 x 2 = , 4 f= 31 )as the optimal solution

of the integer programming problem stated in Eqs. (10.1). Gomory’s method is one in

which the additional constraints are developed in a systematic manner.

10.3.2 Gomory’s Method for All-Integer Programming Problems

In this method the given problem [Eqs. (10.1)] is first solved as an ordinary LP problem

by neglecting the integer requirement. If the optimum values of the variables of the

problem happen to be integers, there is nothing more to be done since the integer

solution is already obtained. On the other hand, if one or more of the basic variables

have fractional values, some additional constraints, known asGomory constraints,

that will force the solution toward an all-integer point will have to be introduced. To

see how the Gomory constraints are generated, let the tableau corresponding to the

optimum (noninteger) solution of the ordinary LP problem be as shown in Table 10.2.

Here it is assumed that there are a total ofm+nvariables (noriginal variables plus

mslack variables). At the optimal solution, the basic variables are represented as

xi (i= 1 , 2 ,... , m)and the nonbasic variables asyj(j = 1 , 2 ,... , n)for convenience.

Gomory’s Constraint. From Table 10.2, choose the basic variable with the largest

fractional value. Let this basic variable bexi. When there is a tie in the fractional

values of the basic variables, any of them can be taken asxi. This variable can be

Table 10.2 Optimum Noninteger Solution of Ordinary LP Problem

Basic Coefficient corresponding to:

variables x 1 x 2... xi... xm y 1 y 2... yj... yn

Objective

function Constants

x 1 1 0 0 0 a 11 a 12 a 1 j a 1 n 0 b 1

x 2 0 1 0 0 a 21 a 22 a 2 j a 2 n 0 b 2

..

.

xi 0 0 1 0 ai 1 ai 2 aij ain 0 bi

..

.

xm 0 0 0 1 am 1 am 2 amj amn 0 bm

f 0 0... 0... 0 c 1 c 2 cj cn 1 f