10.2 Graphical Representation 589
Table 10.1 Integer Programming Methods
Linear programming problems Nonlinear programming problems
All-integer
problem
Mixed-integer
problem
Mixed-integer
problem
Zero–one
problem
Polynomial
programming
problem
General nonlinear
problem
Cutting plane method
Branch-and-bound method
Cutting plane method
Branch-and-bound method
Balas method
All-integer
problem
Generalized penalty function
method
Sequential linear integer
(discrete) programming
method
solve all integer and mixed-integer nonlinear programming problems. The various solu-
tion techniques of solving integer programming problems are summarized in Table 10.1.
All these techniques are discussed briefly in this chapter.
INTEGER LINEAR PROGRAMMING
10.2 Graphical Representation
Consider the following integer programming problem:
Maximizef (X)= 3 x 1 + 4 x 2
subject to
3 x 1 −x 2 ≤ 21
3 x 1 + 11 x 2 ≤ 66
x 1 ≥ 0
x 2 ≥ 0
x 1 andx 2 are integers
(10.1)
The graphical solution of this problem, by ignoring the integer requirements, is shown in
Fig. 10.1. It can be seen that the solution isx 1 = 512 ,x 2 = 412 with a value off= 3412.
Sincethis is a noninteger solution, we truncate the fractional parts and obtain the new
solution asx 1 = , 5 x 2 = , and 4 f=31. By comparing this solution with all other
integer feasible solutions (shown by dots in Fig. 10.1), we find that this solution is
optimum for the integer LP problem stated in Eqs. (10.1).
It is to be noted that truncation of the fractional part of a LP problem will not
always give the solution of the corresponding integer LP problem. This can be illustrated
