Chapter Overview - Chapter 29

A political problem

Suppose that you are a politician trying to win an election. Your district has three different types of area - urban, suburban, and rural. These areas have, respectively, 100,000, 200,000, and 50,000 registered voters. To govern effectively, you would like to win a majority of the votes in each of the three regions. You are honorable and would never consider supporting policies in which you do not believe. You realize, however, that certain issues are building more roads, gun control, farm subsidies, and a gasoline tax dedicated to improved public transit. According to your campaign staff's research, you can estimate how many votes you win or lose from each population segment by spending $1,000 on advertising on each issue. This information appears in the table of Figure 29.1. In this table, each entry describes the number of thousands of either urban, suburban, or rural voters who could be won over by spending $1,000 on advertising in support of a particular issue. Negative entries denote votes that would be lost. Your task is to figure out the minimum amount of money that you need to spend in order to win 50,000 urban votes, 100,000 suburban votes, and 25,000 rural votes.

By trial and error, it is possible to come up with a strategy that will win the required number of votes, but such a strategy may not be the least expensive one. For example, you could devote $20,000 of advertising to building roads, $0 to gun control, $4,000 to farm subsidies, and $9,000 to a gasoline tax. In this case, you would win 20(-2) + 0(8) + 4(0) + 9(10) = 50 thousand urban votes, 20(5) + 0(2) + 4(0) + 9(0) = 100 thousand suburban votes, and 20(3) + 0(-5) + 4(10) + 9(-2) = 82 thousand rural votes. You would win the exact number of votes desired in the urban and suburban areas and more than enough votes in the rural area. (In fact, in the rural area, you have gotten more votes than there are voters!) In order to garner these votes, you would have paid for 20+0+4+9 = 33 thousand dollars of advertising.

Naturally, you may wonder if your strategy was the best possible. That is, could you have achieved your goals while spending less on advertising? Additional trial and error may help you to answer this question, but you would rather have a systematic method for answering such questions. In order to do so, we shall formulate this question mathematically. We introduce 4 variables:

• x₁ is the number of thousands of dollars spent on advertising on building roads,
• x₂ is the number of thousands of dollars spent on advertising on gun control,
• x₃ is the number of thousands of dollars spent on advertising on farm subsidies, and
• x₄ is the number of thousands of dollars spent on advertising on a gasoline tax.

We can write the requirement that we win at least 50,000 urban votes as
-2x₁ + 8x₂ + 0x₃ + 10x₄≥ 50.        (29.1)

Similarly, we can write the requirements that we win at least 100,000 suburban votes and 25,000 rural votes as

5x₁ + 2x₂ + 0x₃ + 0x₄≥ 100        (29.2)
and
3x₁ - 5x₂ + 10x₃ - 2x₄≥ 25        (29.3)

Any setting of the variables x₁, x₂, x₃, x₄ so that inequalities (29.1)-(29.3) are satisfied is a strategy that will win a sufficient number of each type of vote. In order to keep costs as small as possible, we would like to minimize the amount spent on advertising. That is, we would like to minimize the expression

x₁ + x₂ + x₃ + x₄.

Although negative advertising is a common occurrence in political campaigns, there is no such thing as negative-cost advertising. Consequently, we require that

x₁≥ 0, x₂≥ 0, x₃≥ 0, and x₄≥ 0.        (29.5)

Combining inequalities (29.1)-(29.3) and (29.5) with the objective of minimizing (29.4), we obtain what is known as a "linear program." We format this problem as

minimize        x₁ + x₂ + x₃ + x₄        (29.6)

subject to
        -2x₁ + 8x₂ + 0x₃ + 10x₄≥ 50        (29.7)

        5x₁ + 2x₂ + 0x₃ + 0x₄≥ 100        (29.8)

        3x₁ - 5x₂ + 10x₃ - 2x₄≥ 25        (29.9)

        x₁,x₂,x₃,x₄        ≥ 0 .        (29.10)

The solution of this linear program will yield an optimal strategy for the politician.

General linear programs

In the general linear-programming problem, we wish to optimize a linear function subject to a set of linear inequalities. Given a set of real numbers a₁, a₂, …, a_n and a set of variables x₁, x₂, …, x_n, a linear functionf on those variables is defined by

<a onClick="window.open('/olcweb/cgi/pluginpop.cgi?it=gif:: ::/sites/dl/free/0070131511/25344/ch29_overview_1.gif','popWin', 'width=NaN,height=NaN,resizable,scrollbars');" href="#"><img valign="absmiddle" height="16" width="16" border="0" src="/olcweb/styles/shared/linkicons/image.gif"> (0.0K)</a>

If b is a real number and f is a linear function, then then equation

f(x₁, x₂, …, x_n) = b

is a linear equality and the inequalities

f(x₁, x₂, …, x_n) ≤b

and

f(x₁, x₂, …, x_n) ≥b

are linear inequalities. We use the term linear constraints to denote either linear equalities or linear inequalities. In linear programming, we do not allow strict inequalities. Formally, a linear-programming problem is the problem of either minimizing or maximizing a linear function subject to a finite set of linear constraints. If we are to minimize, then we call the linear program a minimization linear program, and if we are to maximize, then we call the linear program a maximization linear program.

This remainder of this chapter will cover the formulation and solution of linear programs. Although there are several polynomial-time algorithms for linear programming, we shall not study them in this chapter. Instead, we shall study the simplex algorithm, which is the oldest linear-programming algorithm. The simplex algorithm does not run in polynomial time in the worst case, but it is fairly efficient and widely used in practice.

An overview of linear programming

In order to describe properties of and algorithms for linear programs, it is convenient to have canonical forms in which to express them. We shall use two forms, standard and slack, in this chapter. They will be defined precisely in Section 29.1. Informally, a linear program in standard form is the maximization of a linear function subject to linear inequalities, whereas a linear program in slack form is the maximization of a linear function subject to linear equalities. We shall typically use standard form when we describe the details of the simplex algorithm. For now, we restrict our attention to maximizing a linear function on n variables subject to a set of m linear inequalities.

Let us first consider the following linear program with two variables:

maximize   x₁ + x₂            (29.11)

subject to
         4x₁ - x₂≤ 8            (29.12)

         2x₁ + x₂≤ 10            (29.13)

         5x₁ - 2x₂≥ -2            (29.14)

             x₁,x₂≥ 0 .             (29.15)

We call any setting of the variables x₁ and x₂ that satisfies all the constraints (29.12)-(29.15) a feasible solution to the linear program. If we graph the constraints in the (x₁,x₂)-Cartesian coordinate system, as in Figure 29.2(a), we see that the set of feasible solutions (shaded in the figure) forms a convex region¹ in the two-dimensional space. We call this convex region the feasible region. The function we wish to maximize is called the objective function. Conceptually, we could evaluate the objective function x₁ + x₂ at each point in the feasible region; we call the value of the objective function at a particular point the objective value. We could then identify a point that has the maximum objective value as an optimal solution. For this example (and for most linear programs), the feasible region contains an infinite number of points, and so we wish to determine an efficient way to find a point that achieves the maximum objective value without explicitly evaluating the objective function at every point in the feasible region.

In two dimensions, we can optimize via a graphical procedure. The set of points for which x₁ + x₂ = z, for any z, is a line with a slope of -1. If we plot x₁ + x₂ = 0, we obtain the line with slope -1 through the origin, as in Figure 29.2(b). The intersection of this line and the feasible region is the set of feasible solutions that have an objective value of 0. In this case, that intersection of the line with the feasible region is the point (0,0). More generally, for any z, the intersection of the line x₁ + x₂ = z and the feasible region is the set of feasible solutions that have objective value z. Figure 29.2(b) shows the lines
x₁ + x₂ = 0, x₁ + x₂ = 4, and x₁ + x₂ = 8. Because the feasible region in Figure 29.2 is bounded, there must be some maximum value z for which the intersection of the line x₁ + x₂ = z and the feasible region is nonempty. Any point at which this occurs is an optimal solution to the linear program, which in this case is the point x₁ = 2 and x₂ = 6 with objective value 8. It is no accident that an optimal solution to the linear program occurred at a vertex of the feasible region. The maximum value of z for which the line x₁ + x₂ = z intersects the feasible region must be on the boundary of the feasible region, and thus the intersection of this line with the boundary of the feasible region is either a vertex or a line segment. If the intersection is a vertex, then there is just one optimal solution, and it is a vertex. If the intersection is a line segment, every point on that line segment must have the same objective value; in particular, both endpoints of the line segment are optimal solutions. Since each endpoint of a line segment is a vertex, there is an optimal solution at a vertex in this case as well.

Although we cannot easily graph linear programs with more than two variables, the same intuition holds. If we have three variables, then each constraint is described by a half-space in three-dimensional space. The intersection of these half-spaces forms the feasible region. The set of points for which the objective function obtains a value z is now a plane. If all coefficients of the objective function are nonnegative, and if the origin is a feasible solution to the linear program, then as we move this plane away from the origin, we find points of increasing objective value. (If the origin is not feasible or if some coefficients in the objective function are negative, the intuitive picture becomes slightly more complicated.) As in two dimensions, because the feasible region is convex, the set of points that achieve the optimal objective value must include a vertex of the feasible region. Similarly, if we have n variables, each constraint defines a half-space in n-dimensional space. The feasible region formed by the intersection of these half-spaces is called a simplex. The objective function is now a hyperplane and, because of convexity, an optimal solution will still occur at a vertex of the simplex.

The simplex algorithm takes as input a linear program and returns an optimal solution. It starts at some vertex of the simplex and performs a sequence of iterations. In each iteration, it moves along an edge of the simplex from a current vertex to a neighboring vertex whose objective value is no smaller than that of the current vertex (and usually is larger). The simplex algorithm terminates when it reaches a local maximum, which is a vertex from which all neighboring vertices have a smaller objective value. Because the feasible region is convex and the objective function is linear, this local optimum is actually a global optimum. In Section 29.4, we shall use a concept called "duality" to show that the solution returned by the simplex algorithm is indeed optimal.

Although the geometric veiw gives a good intuitive view of the operations of the simplex algorithm, we shall not explicitly refer to it when developing the details of the simplex algorithm in Section 29.3. Instead, we take an algebraic view. We first write the given linear program in slack form, which is a set of linear equalities. These linear equalities will express some of the variables, called "basic variables," in terms of other variables, called "nonbasic variables." Moving from one vertex to another will be accomplished by making a basic variable become nonbasic and making a nonbasic variable become basic. This operation is called a "pivot" and, viewed algebraically, is nothing more than a rewriting of the linear program in an equivalent slack form.

The two-variable example described above was a particularly simple one. We shall need to address several more details in this chapter. These issues include identifying linear programs that have no solutions, linear programs that have no finite optimal solution, and linear programs for which the origin is not a feasible solution.

Applications of linear programming

Linear programming has a large number of applications. Any textbook on operations research is filled with examples of linear programming, and it si now a standard tool taught to students in most business schools. The election scenario is one typical example. Two more examples of linear programming are the following:

• An airline wishes to schedule its flight crews. The Federal Aviation Administration imposes many constraints, such as limiting the number of consecutive hours that each crew member can work and insisting that a particular crew work only on one model of aircraft during each month. The airline wants to schedule crews on all of its flights using as few crew members as possible.
• An oil company wants to decide where to drill for oil. Siting a drill at a particular location has an associated cost and, based on geological surveys, an expected payoff of some number of barrels of oil. The company has a limited budget for locating new drills and wants to maximize the amount of oil it expects to find, given this budget.

Linear programs also are useful for modeling and solving graph and combinatorial problems, such as ones that appear in this textbook. We have already seen a special case of linear programming used to solve systems of difference constraints in Section 24.4. In Section 29.2, we shall study how to formulate several graph and network-flow problems as linear programs. In Section 35.4, we shall use linear programming as a tool to find an approximate solution to another graph problem.

Algorithms for linear programming

This chapter studies the simplex algorithm. This algorithm, when implemented carefully, often solves general linear programs quickly in practice. With some carefully contrived inputs, however, the simplex algorithm can require exponential time. The first polynomial-time algorithm for linear programming was the ellipsoid algorithm, which runs slowly in practice. A second class of polynomial-time algorithms are known as interior-point methods. In contrast to the simplex algorithm, which moves along the exterior of the feasible region and maintains a feasible solution that is a vertex of the simplex at each iteration, these algorithms move through the interior of the feasible region. The intermediate solutions, while feasible, are not necessarily vertices of the simplex, but the final solution is a vertex. The first such algorithm was discovered by Karmarkar. For large inputs, the performance of interior-point algorithms can be competitive with, and sometimes faster than, the simplex algorithm.

If we add to a linear program the additional requirement that all variables take on integer values, we have an integer linear program. Exercise 34.5-3 asks you to show that just finding a feasible solution to this problem in NP-hard; since no polynomial-time algorithms are known for any NP-hard problems, there is no known polynomial-time algorithm for integer linear programming. In contrast, a general linear-programming problem is solvable in polynomial time.

In this chapter, if we have a linear program with variables x = (x₁,x₂, …, x_n) and wish to refer to a particular setting of the variables, we shall use the notation
<a onClick="window.open('/olcweb/cgi/pluginpop.cgi?it=gif:: ::/sites/dl/free/0070131511/25344/ch29_overview_2.gif','popWin', 'width=NaN,height=NaN,resizable,scrollbars');" href="#"><img valign="absmiddle" height="16" width="16" border="0" src="/olcweb/styles/shared/linkicons/image.gif"> (0.0K)</a> .