Winston Linear Programming

Integer Programming
Recall that we defined integer programming problems in our discussion of the Divisibility Assumption in Section 3.1. Simply stated, an integer programming problem (IP) is an LP in which some or all of the variables are required to be non-negative integers.† In this chapter (as for LPs in Chapter 3), we find that many real-life situations may be formulated as IPs. Unfortunately,we will also see that IPs are usually much harder to solve than LPs. In Section 9.1, we begin with necessary definitions and some introductory comments about IPs. In Section 9.2, we explain how to formulate integer programming models. We also discuss how to solve IPs on the computer with LINDO, LINGO, and Excel Solver. In Sections 9.3–9.8, we discuss other methods used to solve IPs.

9.1Introduction to Integer Programming
An IP in which all variables are required to be integers is called a pure integer programming problem. For example, max z 3x1 2x2 s.t. x1 x2 6 (1) x1, x2 0, x1, x2 integer is a pure integer programming problem. An IP in which only some of the variables are required to be integers is called a mixed integer programming problem. For example, max z 3x1 2x2 s.t. x1 x2 6x1, x2 0, x1 integer is a mixed integer programming problem (x2 is not required to be an integer). An integer programming problem in which all the variables must equal 0 or 1 is called a 0–1 IP. In Section 9.2, we see that 0–1 IPs occur in surprisingly many situations.‡ The following is an example of a 0–1 IP: max z x1 x2 s.t. x1 2x2 2 (2) 2x1 x2 1 x1, x2 0 or 1 Solution procedures especiallydesigned for 0–1 IPs are discussed in Section 9.7.
†

A nonlinear integer programming problem is an optimization problem in which either the objective function or the left-hand side of some of the constraints are nonlinear functions and some or all of the variables must be integers. Such problems may be solved with LINGO or Excel Solver. ‡ Actually, any pure IP can be reformulated as an equivalent0–1 IP (Section 9.7).

The concept of LP relaxation of an integer programming problem plays a key role in the solution of IPs.
DEFINITION s

The LP obtained by omitting all integer or 0–1 constraints on variables is called the LP relaxation of the IP. s For example, the LP relaxation of (1) is max z 3x1 2x2 s.t. x1 x2 6 x1, x2 0 and the LP relaxation of (2) is max z x1 s.t. x1 s.t. 2x1 x1,x2 x2 2x2 x2 0 2 1
(1 )

(2 )

Any IP may be viewed as the LP relaxation plus additional constraints (the constraints that state which variables must be integers or be 0 or 1). Hence, the LP relaxation is a less constrained, or more relaxed, version of the IP. This means that the feasible region for any IP must be contained in the feasible region for the corresponding LP relaxation. For anyIP that is a max problem, this implies that Optimal z-value for LP relaxation optimal z-value for IP
(3)

This result plays a key role when we discuss the solution of IPs. To shed more light on the properties of integer programming problems, we consider the following simple IP: max z 21x1 11x2 s.t. 7x1 4x2 13 x1, x2 0; x1, x2 integer
(4)

From Figure 1, we see that the feasible region forthis problem consists of the following set of points: S {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1)}. Unlike the feasible region for any LP, the one for (4) is not a convex set. By simply computing and comparing the z-values for each of the six points in the feasible region, we find the optimal solution to (4) is z 33, x1 0, x2 3. If the feasible region for a pure IP’s LP relaxation is bounded, asin (4), then the feasible region for the IP will consist of a finite number of points. In theory, such an IP could be solved (as described in the previous paragraph) by enumerating the z-values for each feasible point and determining the feasible point having the largest z-value. The problem with this approach is that most actual IPs have feasible regions consisting of billions of feasible...