Integer Programming

Integer programming problem is a special type of Linear programming problem, in which

some or all the decision variables are integer, i.e.

There are two methods to find the solution of integer programming problems:
(1) Branch and Bound Method: it is based on graphical method and limited to
incorporate only two decision variables.
(2) Gomary Cutting Plane method: It is based on simplex technique and able to
incorporate many decision variables.

Branch and Bound Method

Example 1

Soln:

Figure 1: Graphical Solution of Example 1

Solving the constraints

No feasible
zone of
solution

Figure 2: Branch and Bound of Example 1

This is the case of multiple solution at points C and D; Max z = 6, at (0,2) or (1,2)
Note: Solution of Linear Programming problems occur at only vertices of the polygon,
however, the solution of Integer programming problems may occur at any point of the
boundry.
Example 2

Soln: Solving constraints 1 and 2, constraint 3 is redundant as it lies much above the
feasible zone (Refer Figure 2.)

Figure 3: Graphical Solution of Example 2

Solving Constraints 1 and 2, we get the point B (9/2,7/2) as
 No feasible
zone of
solution

Figure 4: Branch and Bound of Example 2

Example 3

On Solving the constraints, we get the points A (4,10/3), B (4,6), C (12/5,6).

 Figure 5: Graphical solution of Example 3

No feasible
zone of
solution

Figure 6: Branch and Bound of Example 3

Minimum value of Z =27 at point G (3,5).
Gomary Cutting Plane Method
Example 4

Soln:
Simplex Format

Table 1
Basis Value X1 X2 S1 S2 Ratio
R1 S1 12 3 2 1 0 12/3=4
R2 S2 2 0 1 0 1 2/0=∞
Ro z 0 -1 -1 0 0
Iteration 1
1. In Table 1, -1 is the most negative in the objective row, thus, X1 becomes the
entering variable.
2. Ratios of values and elements of key column are 4 and ∞ . 4 is the least
positive ratio, thus, S1 becomes the leaving variable.
3. The element 3, in R1 row and X1 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
New Key row:
New number = Old number/Key number;
New other rows,
New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
5. Now all the numbers in the key column will be zero except key number which
will be 1.
Table 2
Basis Value X1 X2 S1 S2 Ratio
R1 X1 4 1 2/3 1/3 0 6
R2 S2 2 0 1 0 1 2/1=2
 Ro z 4 0 -1/3 1/3 0

Iteration 2
1. In Table 2, -1/3 is the most negative in the objective row, thus, X 2 becomes
the entering variable.
2. Ratios of values and elements of key column are 6 and 2 . 2 is the least
positive ratio, thus, S2 becomes the leaving variable.
3. The element 1, in R2 row and X2 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
a. New Key row:
b. New number = Old number/Key number;
c. New other rows,
5. New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
6. Now all the numbers in the key column will be zero except key number which
will be 1.
Table 3
Basis Value X1 X2 S1 S2 Ratio
R1 X1 8/3 1 0 1/3 -2/3
R2 X2 2 0 1 0 1
Ro z 14/3 0 0 1/3 1/3
All elements in the objective row are positive, thus solution is optimal.

Choose the variable for cutting plane whose fractional value is large.
Max {2/3,0} corresponding to x1.
Choose the row x1 in Table 3.
Table 4
Basis Value X1 X2 S1 S2 Sg Ratio
R1 X1 8/3 1 0 1/3 -2/3 0 8
R2 X2 2 0 1 0 1 0 ∞
R3 Sg -2/3 0 0 -1/3 -1/3 1 2
Ro z 14/3 0 0 1/3 1/3 0

Iteration 3
1. In Table 4, Divide the Objective row by the negative row elements R3. and find
the least negative ratio (numerically). Here both the ratios are same. -1 is the
least negative in the objective row, thus, S1 or S2 becomes the entering
variable. Here, we have considered S1.
2. Ratios of values and elements of key column are 8, ∞, and 2. 2 is the least
positive ratio, thus, S1 becomes the leaving variable.
3. The element -1/3, in R3 row and S1 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
a. New Key row:
b. New number = Old number/Key number;
c. New other rows,
5. New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
6. Now all the numbers in the key column will be zero except key number which
will be 1.
Table 5
Basis Value X1 X2 S1 S2 Sg Ratio
R1 X1 2 1 0 0 0 1
R2 X2 2 0 1 0 1 0
R3 Sg 2 0 0 1 1 -3
Ro z 4 0 0 0 0 1
Max Z = 4; X1 = 2, X2 =2 Ans.
Example 5

Soln:
Simplex Format

Table 1
Basis Value X1 X2 S1 S2 S3 Ratio
R1 S1 7 1 1 1 0 0 7/1=7
R2 S2 11 2 0 0 1 0 11/0=∞
R3 S3 7 0 2 0 0 1 7/2
Ro z 0 -1 -2 0 0 0

Iteration 1
1. In Table 1, -2 is the most negative in the objective row, thus, X2 becomes the
entering variable.
2. Ratios of values and elements of key column are 7, ∞, and 7/2 . 7/2 is the
least positive ratio, thus, S3 becomes the leaving variable.
3. The element 2, in R3 row and X2 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
a. New Key row:
b. New number = Old number/Key number;
c. New other rows,
5. New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
6. Now all the numbers in the key column will be zero except key number which
will be 1.
 Table 2
Basis Value X1 X2 S1 S2 S3 Ratio
R1 S1 7/2 1 0 1 0 -1/2 7/2
R2 S2 11 2 0 0 1 0 11/2
R3 X2 7/2 0 1 0 0 1/2 ∞
Ro z 7 -1 0 0 0 1

Iteration 2
1. In Table 2, -1 is the most negative in the objective row, thus, X1 becomes the
entering variable.
2. Ratios of values and elements of key column are 7/2, 11/2, and ∞. 7/2 is the
least positive ratio, thus, S1 becomes the leaving variable.
3. The element 1, in R1 row and X1 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
a. New Key row:
b. New number = Old number/Key number;
c. New other rows,
5. New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
6. Now all the numbers in the key column will be zero except key number which
will be 1.
Table 3
Basis Value X1 X2 S1 S2 S3 Ratio
R1 X1 7/2 1 0 1 0 -1/2
R2 S2 4 0 -2 -2 1 1
R3 X2 7/2 0 1 0 0 1/2
Ro z 21/2 0 0 1 0 1/2
All elements in the objective row are positive, thus solution is optimal.

Choose the variable for cutting plane whose fractional value is large.
Max {1/2,1/2}. Choose any one X1or X2 as the fractional value for both is same. Here, we
choose X1.

Choose the row R1 in Table 3.

 Table 4
Basis Value X1 X2 S1 S2 S3 Sg1 Ratio
R1 X1 7/2 1 0 1 0 -1/2 0 -ve
R2 S2 4 0 -2 -2 1 1 0 4
R3 X2 7/2 0 1 0 0 1/2 0 7
R4 Sg1 -1/2 0 0 0 0 -1/2 1 1
Ro z 21/2 0 0 1 0 1/2 0

Iteration 3
1. In Table 4, Divide the Objective row by the negative row elements R3. -1 is the
least negative (numerically) in the objective row, thus, S3 becomes the
entering variable.
2. Ratios of values and elements of key column are -ve, 4, 7, and 1. 1 is the
least positive ratio, thus, Sg1 becomes the leaving variable.
3. The element -1/2, in R4 row and S3 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
a. New Key row:
b. New number = Old number/Key number;
c. New other rows,
5. New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
6. Now all the numbers in the key column will be zero except key number which
will be 1.
Table 5
Basis Value X1 X2 S1 S2 S3 Sg1 Ratio
R1 X1 4 1 0 1 0 0 -1
R2 S2 4 0 0 -2 1 0 2
R3 X2 3 0 1 0 0 0 1
R4 S3 1 0 0 0 0 1 -2
Ro z 10 0 0 1 0 0 1
Max Z = 10; X1 = 4, X2 = 3 Ans.
Example 6

Soln:
Simplex Format

Table 1
Basis Value X1 X2 S1 S2 S3 Ratio
R1 S1 6 -1 3 1 0 0 2
R2 S2 35 7 1 0 1 0 35
R3 S3 7 0 1 0 0 1 7
Ro z 0 -7 -9 0 0 0

Iteration 1
1. In Table 1, -9 is the most negative in the objective row, thus, X2 becomes the
entering variable.
2. Ratios of values and elements of key column are 2, 35, and 7. 2 is the least
positive ratio, thus, S1 becomes the leaving variable.
3. The element 2, in R1 row and X2 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
a. New Key row:
 b. New number = Old number/Key number;
c. New other rows,
5. New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
6. Now all the numbers in the key column will be zero except key number which
will be 1.
Table 2
Basis Value X1 X2 S1 S2 S3 Ratio
R1 X2 2 -1/3 1 1/3 0 0 -ve
R2 S2 33 22/3 0 -1/3 1 0 9/2
R3 S3 5 1/3 0 -1/3 0 1 15
Ro z 18 -10 0 3 0 0

Iteration 2
1. In Table 2, -10 is the most negative in the objective row, thus, X1 becomes the
entering variable.
2. Ratios of values and elements of key column are -ve, 9/2, and 15. 9/2 is the
least positive ratio, thus, S1 becomes the leaving variable.
3. The element 22/3, in R2 row and X1 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
a. New Key row:
b. New number = Old number/Key number;
c. New other rows,
5. New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
6. Now all the numbers in the key column will be zero except key number which
will be 1.
Table 3
Basis Value X1 X2 S1 S2 S3 Ratio
R1 X2 7/2 0 1 7/22 1/22 0
R2 X1 9/2 1 0 -1/22 3/22 0
R3 S3 7/2 0 0 -7/22 -1/22 1
Ro z 63 0 0 28/11 15/11 0
All elements in the objective row are positive, thus solution is optimal.

Choose the variable for cutting plane whose fractional value is large.
Max {1/2,1/2}. Choose any one X1or X2 as the fractional value for both is same. Here, we
choose X2.

Choose the row R1 in Table 3.

Table 4
Basis Value X1 X2 S1 S2 S3 Sg1 Ratio
R1 X2 7/2 0 1 7/22 1/22 0 0 11
R2 X1 9/2 1 0 -1/22 3/22 0 0 -33
R3 S3 7/2 0 0 -7/22 -1/22 1 0 -11
R4 Sg1 -1/22 0 0 -7/22 -1/22 0 1 1/7
Ro z 63 0 0 28/11 15/11 0 0

Iteration 3
1. In Table 4, Divide the Ro by R4, and find the least negative (numerically)
between 28/11×-22/7= -8 and 15/11×-22/1=-30. -8 is the least negative ratio,
thus -7/22 in the row R4 is considered as key number. S1 becomes the
entering variable.
2. Ratios of values and elements of key column are -ve, 11, -33, -11, and 1/7.
1/7 is the least positive ratio, thus, Sg1 becomes the leaving variable.
3. The element -7/22, in R4 row and S1 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
a. New Key row:
b. New number = Old number/Key number;
c. New other rows,
5. New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
6. Now all the numbers in the key column will be zero except key number which
will be 1.
Table 5
Basis Value X1 X2 S1 S2 S3 Sg1 Ratio
R1 X2 3 0 1 0 0 0 1
R2 X1 32/7 1 0 0 1/7 0 -1/7
R3 S3 4 0 0 0 0 1 -1
R4 Sg1 11/7 0 0 1 1/7 0 -22/7
Ro z 59 0 0 0 1 0 8

Choose the row X1 as Gomary Cutting Plane.

Table 6
Basis Value X1 X2 S1 S2 S3 Sg1 Sg2 Ratio
R1 X2 3 0 1 0 0 0 1 0 ∞
R2 X1 32/7 1 0 0 1/7 0 -1/7 0 32
R3 S3 4 0 0 0 0 1 -1 0 ∞
R4 Sg1 11/7 0 0 1 1/7 0 -22/7 0 11
R5 Sg2 -4/7 0 0 0 -1/7 0 -6/7 1 4
Ro z 59 0 0 0 1 0 8 0
Iteration 4
1. In Table 4, Divide the R0 row elements with R5 (-ve) row and find the
numerically least negative elements in Ro after division. We get two values -7
and -28/3, thus, -1/7 is is considered as the key number in the row R4, aS2
becomes the entering variable.
2. Ratios of values and elements of key column are ∞, 32, ∞, 11, and 4. 4 is the
least positive ratio, thus, Sg1 becomes the leaving variable.
3. The element -1/7, in R4 row and S2 column becomes the key number.
4. After iteration, all the old number (co-efficient) of the old table will be changed
as:
a. New Key row:
b. New number = Old number/Key number;
c. New other rows,
5. New number = Old number – (Corresponding number in Key Column ×
corresponding number in Key row)/ Key number
6. Now all the numbers in the key column will be zero except key number which
will be 1.
Table 7
Basis Value X1 X2 S1 S2 S3 Sg1 Sg2 Ratio
R1 X2 3 0 1 0 0 0 1 0
R2 X1 4 1 0 0 0 0 5/7 1
R3 S3 4 0 0 0 0 1 -1 0
R4 Sg1 1 0 0 1 0 0 -16/7 1
R5 Sg2 4 0 0 0 1 0 -6 -7
Ro z 55 0 0 0 0 0 2 7

Max Z = 55; X1 = 4, X2 = 3 Ans.