10.3 Gomory’s Cutting Plane Method 599
Since onlyarjcorresponding to columny 2 is negative, the pivot element
will be− 111 in thes 2 row. The pivot operation on this element leads to the
following tableau:
Basic Coefficients of variables
variables x 1 x 2 y 1 y 2 −f s 1 s 2 bi
x 1 1 0 0 0 0 1 0 5
x 2 0 1 0 0 0 0 1 4
y 1 0 0 1 0 0 − 3 1 1
−f 0 0 0 0 1 3 4 31
y 2 0 0 0 1 0 − 3 − 11 7
The solution given by this tableau isx 1 = , 5 x 2 = , 4 y 1 = , 1 y 2 = , and 7
f= −31, which can be seen to satisfy the integer requirement. Hence this is
the desired solution.
10.3.3 Gomory’s Method for Mixed-Integer Programming Problems
The method discussed in Section 10.3.2 is applicable to solve all integer programming
problems where both the decision and slack variables are restricted to integer values in
the optimal solution. In the mixed-integer programming problems, only a subset of the
decision and slack variables are restricted to integer values. The procedure for solving
mixed-integer programming problems is similar to that of all-integer programming
problems in many respects.
Solution Procedure. As in the case of an all-integer programming problem, the first
step involved in the solution of a mixed-integer programming problem is to obtain an
optimal solution of the ordinary LP problem without considering the integer restrictions.
If the values of the basic variables, which were restricted to integer values, happen to
be integers in this optimal solution, there is nothing more to be done. Otherwise, a
Gomory constraint is formulated by taking the integer-restricted basic variable, which
has the largest fractional value in the optimal solution of the ordinary LP problem.
Letxi be the basic variable that has the largest fractional value in the optimal
solution (as shown in Table 10.2), although it is restricted to take on only integer
values. If the nonbasic variables are denoted asyj, j= 1 , 2 ,... , n, the basic variable
xican be expressed as (from Table 10.2)
xi=bi−
∑n
j= 1
aijyj (10.2)
We can write
bi=bˆi+βi (10.3)
wherebˆiis the integer obtained by truncating the fractional part ofbiandβi is the
fractional part ofbi. By defining
aij=a+ij+ai−j (10.10)
