7.1 An introduction to linear programming

Chapter 7: Linear programming and reductions

Many of the problems for which we want algorithms are optimization tasks: the shortest path, the cheapest spanning tree, the longest increasing subsequence, and so on. In such cases, we seek a solution that (1) satisfies certain constraints (for instance, the path must use edges of the graph and lead from s to t, the tree must touch all nodes, the subsequence must be increasing); and (2) is the best possible, with respect to some well-defined criterion, among all solutions that satisfy these constraints.

Linear programming describes a broad class of optimization tasks in which both the constraints and the optimization criterion are linear functions. It turns out an enormous number of problems can be expressed in this way.

Given the vastness of its topic, this chapter is divided into several parts, which can be read separately subject to the following dependencies.

In a linear programming problem we are given a set of variables, and we want to assign real values to them so as to (1) satisfy a set of linear equations and/or linear inequalities involving these variables and (2) maximize or minimize a given linear objective function.

7.1.1 Example: profit maximization

A boutique chocolatier has two products: its flagship assortment of triangular chocolates, called Pyramide, and the more decadent and deluxe Pyramide Nuit. How much of each should it produce to maximize profits? Let’s say it makes $x _ { 1 }$ boxes of Pyramide per day, at a profit of

Figure 7.1 ( $a$ ) The feasible region for a linear program. ( $b$ ) Contour lines of the objective function: $x _ { 1 } + 6 x _ { 2 } = c$ for different values of the profit c.

( $a$ )

$1 each, and $x _ { 2 }$ boxes of Nuit, at a more substantial profit of $6 apiece; $x _ { 1 }$ and $x _ { 2 }$ are unknown values that we wish to determine. But this is not all; there are also some constraints on $x _ { 1 }$ and $x _ { 2 }$ that must be accommodated (besides the obvious one, $x _ { 1 } , x _ { 2 } \ge 0 )$ . First, the daily demand for these exclusive chocolates is limited to at most 200 boxes of Pyramide and 300 boxes of Nuit. Also, the current workforce can produce a total of at most 400 boxes of chocolate per day. What are the optimal levels of production?

We represent the situation by a linear program, as follows.

Objective function

Constraints

\begin{array}{r l} \max x _ {1} + 6 x _ {2} \\ x _ {1} & \leq 2 0 0 \\ x _ {2} & \leq 3 0 0 \\ x _ {1} + x _ {2} & \leq 4 0 0 \\ x _ {1}, x _ {2} & \geq 0 \end{array}

A linear equation in $x _ { 1 }$ and $x _ { 2 }$ defines a line in the two-dimensional (2D) plane, and a linear inequality designates a half-space, the region on one side of the line. Thus the set of all feasible solutions of this linear program, that is, the points $( x _ { 1 } , x _ { 2 } )$ which satisfy all constraints, is the intersection of five half-spaces. It is a convex polygon, shown in Figure 7.1.

We want to find the point in this polygon at which the objective function—the profit—is maximized. The points with a profit of c dollars lie on the line $x _ { 1 } + 6 x _ { 2 } = c ,$ which has a slope of $- 1 / 6$ and is shown in Figure 7.1 for selected values of c. As c increases, this “profit line” moves parallel to itself, up and to the right. Since the goal is to maximize $^ { c , }$ we must move the line as far up as possible, while still touching the feasible region. The optimum solution will be the very last feasible point that the profit line sees and must therefore be a vertex of the polygon, as shown in the figure. If the slope of the profit line were different, then its last contact with the polygon could be an entire edge rather than a single vertex. In this case, the optimum solution would not be unique, but there would certainly be an optimum vertex.

It is a general rule of linear programs that the optimum is achieved at a vertex of the feasible region. The only exceptions are cases in which there is no optimum; this can happen in two ways:

The linear program is infeasible; that is, the constraints are so tight that it is impossible to satisfy all of them. For instance,

x \leq 1, x \geq 2.

The constraints are so loose that the feasible region is unbounded, and it is possible to achieve arbitrarily high objective values. For instance,

\begin{array}{c} \max x _ {1} + x _ {2} \\ x _ {1}, x _ {2} \geq 0 \end{array}

Solving linear programs

Linear programs (LPs) can be solved by the simplex method, devised by George Dantzig in 1947. We shall explain it in more detail in Section 7.6, but briefly, this algorithm starts at a vertex, in our case perhaps (0, 0), and repeatedly looks for an adjacent vertex (connected by an edge of the feasible region) of better objective value. In this way it does hill-climbing on the vertices of the polygon, walking from neighbor to neighbor so as to steadily increase profit along the way. Here’s a possible trajectory.

Upon reaching a vertex that has no better neighbor, simplex declares it to be optimal and halts. Why does this local test imply global optimality? By simple geometry—think of the profit line passing through this vertex. Since all the vertex’s neighbors lie below the line, the rest of the feasible polygon must also lie below this line.

More products

Encouraged by consumer demand, the chocolatier decides to introduce a third and even more exclusive line of chocolates, called Pyramide Luxe. One box of these will bring in a profit of $13.

Figure 7.2 The feasible polyhedron for a three-variable linear program.

Let $x _ { 1 } , x _ { 2 } , x _ { 3 }$ denote the number of boxes of each chocolate produced daily, with $x _ { 3 }$ referring to Luxe. The old constraints on $x _ { 1 }$ and $x _ { 2 }$ persist, although the labor restriction now extends to $x _ { 3 }$ as well: the sum of all three variables can be at most 400. What’s more, it turns out that Nuit and Luxe require the same packaging machinery, except that Luxe uses it three times as much, which imposes another constraint $x _ { 2 } + 3 x _ { 3 } \leq 6 0 0$ . What are the best possible levels of production?

Here is the updated linear program.

\begin{array}{c} \max x _ {1} + 6 x _ {2} + 1 3 x _ {3} \\ x _ {1} \leq 2 0 0 \\ x _ {2} \leq 3 0 0 \\ x _ {1} + x _ {2} + x _ {3} \leq 4 0 0 \\ x _ {2} + 3 x _ {3} \leq 6 0 0 \\ x _ {1}, x _ {2}, x _ {3} \geq 0 \end{array}

The space of solutions is now three-dimensional. Each linear equation defines a 3D plane, and each inequality a half-space on one side of the plane. The feasible region is an intersection of seven half-spaces, a polyhedron (Figure 7.2). Looking at the figure, can you decipher which inequality corresponds to each face of the polyhedron?

A profit of c corresponds to the plane $x _ { 1 } + 6 x _ { 2 } + 1 3 x _ { 3 } = c .$ . As c increases, this profit-plane moves parallel to itself, further and further into the positive orthant until it no longer touches the feasible region. The point of final contact is the optimal vertex: (0, 300, 100), with total profit $3100.

How would the simplex algorithm behave on this modified problem? As before, it would move from vertex to vertex, along edges of the polyhedron, increasing profit steadily. A possible trajectory is shown in Figure 7.2, corresponding to the following sequence of vertices and profits:

\begin{array}{c c c c c c c c} (0, 0, 0) & \longrightarrow & (2 0 0, 0, 0) & \longrightarrow & (2 0 0, 2 0 0, 0) & \longrightarrow & (2 0 0, 0, 2 0 0) & \longrightarrow & (0, 3 0 0, 1 0 0) \\ \mathbb {S} 0 & & \mathbb {S} 2 0 0 & & \mathbb {S} 1 4 0 0 & & \mathbb {S} 2 8 0 0 & \longrightarrow & \mathbb {S} 3 1 0 0 \end{array}

Finally, upon reaching a vertex with no better neighbor, it would stop and declare this to be the optimal point. Once again by basic geometry, if all the vertex’s neighbors lie on one side of the profit-plane, then so must the entire polyhedron.

Box: A magic trick called duality

Here is why you should believe that (0, 300, 100), with a total profit of $3100, is the optimum: Look back at the linear program. Add the second inequality to the third, and add to them the fourth multiplied by 4. The result is the inequality $x _ { 1 } + 6 x _ { 2 } + 1 3 x _ { 3 } \leq 3 1 0 0$

Do you see? This inequality says that no feasible solution (values $x _ { 1 } , x _ { 2 } , x _ { 3 }$ satisfying the constraints) can possibly have a profit greater than 3100. So we must indeed have found the optimum! The only question is, where did we get these mysterious multipliers (0, 1, 1, 4) for the four inequalities?

In Section 7.4 we’ll see that it is always possible to come up with such multipliers by solving another LP! Except that (it gets even better) we do not even need to solve this other LP, because it is in fact so intimately connected to the original one—it is called the dual— that solving the original LP solves the dual as well! But we are getting far ahead of our story.

What if we add a fourth line of chocolates, or hundreds more of them? Then the problem becomes high-dimensional, and hard to visualize. Simplex continues to work in this general setting, although we can no longer rely upon simple geometric intuitions for its description and justification. We will study the full-fledged simplex algorithm in Section 7.6.

In the meantime, we can rest assured in the knowledge that there are many professional, industrial-strength packages that implement simplex and take care of all the tricky details like numeric precision. In a typical application, the main task is therefore to correctly express the problem as a linear program. The package then takes care of the rest.

With this in mind, let’s look at a high-dimensional application.

7.1.2 Example: production planning

This time, our company makes handwoven carpets, a product for which the demand is extremely seasonal. Our analyst has just obtained demand estimates for all months of the next calendar year: $d _ { 1 } , d _ { 2 } , \ldots , d _ { 1 2 }$ . As feared, they are very uneven, ranging from 440 to 920.

Here’s a quick snapshot of the company. We currently have 30 employees, each of whom makes 20 carpets per month and gets a monthly salary of $2,000. We have no initial surplus of carpets.

How can we handle the fluctuations in demand? There are three ways:

Overtime, but this is expensive since overtime pay is 80% more than regular pay. Also, workers can put in at most 30% overtime.
Hiring and firing, but these cost $320 and $400, respectively, per worker.
Storing surplus production, but this costs $8 per carpet per month. We currently have no stored carpets on hand, and we must end the year without any carpets stored.

This rather involved problem can be formulated and solved as a linear program!

A crucial first step is defining the variables.

$w _ { i }$ = number of workers during ith month; $w _ { 0 } = 3 0 .$

$x _ { i }$ = number of carpets made during ith month.

$o _ { i }$ = number of carpets made by overtime in month i.

$h _ { i } , f _ { i }$ = number of workers hired and fired, respectively, at beginning of month i.

$s _ { i }$ = number of carpets stored at end of month i; $s _ { 0 } = 0 .$

All in all, there are 72 variables (74 if you count $w _ { 0 }$ and $s _ { 0 } )$ .

We now write the constraints. First, all variables must be nonnegative:

w _ {i}, x _ {i}, o _ {i}, h _ {i}, f _ {i}, s _ {i} \geq 0, i = 1, \ldots , 1 2.

The total number of carpets made per month consists of regular production plus overtime:

x _ {i} = 2 0 w _ {i} + o _ {i}

(one constraint for each $i = 1 , \ldots , 1 2 )$ . The number of workers can potentially change at the start of each month:

w _ {i} = w _ {i - 1} + h _ {i} - f _ {i}.

The number of carpets stored at the end of each month is what we started with, plus the number we made, minus the demand for the month:

s _ {i} = s _ {i - 1} + x _ {i} - d _ {i}.

And overtime is limited:

o _ {i} \leq 6 w _ {i}.

Finally, what is the objective function? It is to minimize the total cost:

\min 2 0 0 0 \sum_ {i} w _ {i} + 3 2 0 \sum_ {i} h _ {i} + 4 0 0 \sum_ {i} f _ {i} + 8 \sum_ {i} s _ {i} + 1 8 0 \sum_ {i} o _ {i},

a linear function of the variables. Solving this linear program by simplex should take less than a second and will give us the optimum business strategy for our company.

Figure 7.3 A communications network between three users A, $B$ , and C. Bandwidths are shown.

Well, almost. The optimum solution might turn out to be fractional; for instance, it might involve hiring 10.6 workers in the month of March. This number would have to be rounded to either 10 or 11 in order to make sense, and the overall cost would then increase correspondingly. In the present example, most of the variables take on fairly large (double-digit) values, and thus rounding is unlikely to affect things too much. There are other LPs, however, in which rounding decisions have to be made very carefully in order to end up with an integer solution of reasonable quality.

In general, there is a tension in linear programming between the ease of obtaining fractional solutions and the desirability of integer ones. As we shall see in Chapter 8, finding the optimum integer solution of an LP is an important but very hard problem, called integer linear programming.

7.1.3 Example: optimum bandwidth allocation

Next we turn to a miniaturized version of the kind of problem a network service provider might face.

Suppose we are managing a network whose lines have the bandwidths shown in Figure 7.3, and we need to establish three connections: between users A and B, between B and C, and between A and C. Each connection requires at least two units of bandwidth, but can be assigned more. Connection A–B pays $3 per unit of bandwidth, and connections B–C and A–C pay $2 and $4, respectively.

Each connection can be routed in two ways, a long path and a short path, or by a combination: for instance, two units of bandwidth via the short route, one via the long route. How do we route these connections to maximize our network’s revenue?

This is a linear program. We have variables for each connection and each path (long or short); for example, $x _ { A B }$ is the short-path bandwidth allocated to the connection between A and B, and $x _ { A B } ^ { \prime }$ the long-path bandwidth for this same connection. We demand that no edge’s bandwidth is exceeded and that each connection gets a bandwidth of at least 2 units.

\max 3 x _ {A B} + 3 x _ {A B} ^ {\prime} + 2 x _ {B C} + 2 x _ {B C} ^ {\prime} + 4 x _ {A C} + 4 x _ {A C} ^ {\prime}

\begin{array}{r l r} x _ {A B} + x _ {A B} ^ {\prime} + x _ {B C} + x _ {B C} ^ {\prime} \leq 1 0 & [ \text {edge} (b, B) ] \\ x _ {A B} + x _ {A B} ^ {\prime} + x _ {A C} + x _ {A C} ^ {\prime} \leq 1 2 & [ \text {edge} (a, A) ] \\ x _ {B C} + x _ {B C} ^ {\prime} + x _ {A C} + x _ {A C} ^ {\prime} \leq 8 & [ \text {edge} (c, C) ] \\ x _ {A B} + x _ {B C} ^ {\prime} + x _ {A C} ^ {\prime} \leq 6 & [ \text {edge} (a, b) ] \\ x _ {A B} ^ {\prime} + x _ {B C} + x _ {A C} ^ {\prime} \leq 1 3 & [ \text {edge} (b, c) ] \\ x _ {A B} ^ {\prime} + x _ {B C} ^ {\prime} + x _ {A C} \leq 1 1 & [ \text {edge} (a, c) ] \\ x _ {A B} + x _ {A B} ^ {\prime} \geq 2 \\ x _ {B C} + x _ {B C} ^ {\prime} \geq 2 \\ x _ {A C} + x _ {A C} ^ {\prime} \geq 2 \\ x _ {A B}, x _ {A B} ^ {\prime}, x _ {B C}, x _ {B C} ^ {\prime}, x _ {A C}, x _ {A C} ^ {\prime} \geq 0 \end{array}

Even a tiny example like this one is hard to solve on one’s own (try it!), and yet the optimal solution is obtained instantaneously via simplex:

x _ {A B} = 0, x _ {A B} ^ {\prime} = 7, x _ {B C} = x _ {B C} ^ {\prime} = 1. 5, x _ {A C} = 0. 5, x _ {A C} ^ {\prime} = 4. 5.

This solution is not integral, but in the present application we don’t need it to be, and thus no rounding is required. Looking back at the original network, we see that every edge except a–c is used at full capacity.

One cautionary observation: our LP has one variable for every possible path between the users. In a larger network, there could easily be exponentially many such paths, and therefore this particular way of translating the network problem into an LP will not scale well. We will see a cleverer and more scalable formulation in Section 7.2.

Here’s a parting question for you to consider. Suppose we removed the constraint that each connection should receive at least two units of bandwidth. Would the optimum change?

Box: Reductions

Sometimes a computational task is sufficiently general that any subroutine for it can also be used to solve a variety of other tasks, which at first glance might seem unrelated. For instance, we saw in Chapter 6 how an algorithm for finding the longest path in a dag can, surprisingly, also be used for finding longest increasing subsequences. We describe this phenomenon by saying that the longest increasing subsequence problem reduces to the longest path problem in a dag. In turn, the longest path in a dag reduces to the shortest path in a dag; here’s how a subroutine for the latter can be used to solve the former:

function LONGEST PATH( $G$ )

negate all edge weights of G

return SHORTEST PATH( $G$ )

Let’s step back and take a slightly more formal view of reductions. If any subroutine for task Q can also be used to solve P, we say P reduces to Q. Often, P is solvable by a single call to Q’s subroutine, which means any instance x of P can be transformed into an instance y of Q such that P( $x$ ) can be deduced from Q( $y$ ):

(Do you see that the reduction from P = LONGEST PATH to Q = SHORTEST PATH follows this schema?) If the pre- and postprocessing procedures are efficiently computable then this creates an efficient algorithm for P out of any efficient algorithm for Q!

Reductions enhance the power of algorithms: Once we have an algorithm for problem Q (which could be shortest path, for example) we can use it to solve other problems. In fact, most of the computational tasks we study in this book are considered core computer science problems precisely because they arise in so many different applications, which is another way of saying that many problems reduce to them. This is especially true of linear programming.

7.1.4 Variants of linear programming

As evidenced in our examples, a general linear program has many degrees of freedom.

It can be either a maximization or a minimization problem.
Its constraints can be equations and/or inequalities.
The variables are often restricted to be nonnegative, but they can also be unrestricted in sign.

We will now show that these various LP options can all be reduced to one another via simple transformations. Here’s how.

To turn a maximization problem into a minimization (or vice versa), just multiply the coefficients of the objective function by 1.

2a. To turn an inequality constraint like $\textstyle \sum _ { i = 1 } ^ { n } a _ { i } x _ { i } \leq b$ into an equation, introduce a new variable s and use

\begin{array}{r c l} \sum_ {i = 1} ^ {n} a _ {i} x _ {i} + s & = & b \\ s & \geq & 0. \end{array}

This s is called the slack variable for the inequality. As justification, observe that a vector $( x _ { 1 } , \ldots , x _ { n } )$ satisfies the original inequality constraint if and only if there is some $s \geq 0$ for which it satisfies the new equality constraint.

2b. To change an equality constraint into inequalities is easy: rewrite $a x = b$ as the equivalent pair of constraints $a x \leq b$ and $a x \geq b .$

Finally, to deal with a variable x that is unrestricted in sign, do the following:

Introduce two nonnegative variables, $x ^ { + } , x ^ { - } \geq 0 .$

Replace x, wherever it occurs in the constraints or the objective function, by $x ^ { + } - x ^ { - }$

This way, x can take on any real value by appropriately adjusting the new variables. More precisely, any feasible solution to the original LP involving x can be mapped to a feasible solution of the new LP involving $x ^ { + } , x ^ { - }$ , and vice versa.

By applying these transformations we can reduce any LP (maximization or minimization, with both inequalities and equations, and with both nonnegative and unrestricted variables) into an LP of a much more constrained kind that we call the standard form, in which the variables are all nonnegative, the constraints are all equations, and the objective function is to be minimized.

For example, our first linear program gets rewritten thus:

\begin{array}{c} \max x _ {1} + 6 x _ {2} \\ x _ {1} \leq 2 0 0 \\ x _ {2} \leq 3 0 0 \\ x _ {1} + x _ {2} \leq 4 0 0 \\ x _ {1}, x _ {2} \geq 0 \end{array}

\begin{array}{c} \min - x _ {1} - 6 x _ {2} \\ x _ {1} + s _ {1} = 2 0 0 \\ x _ {2} + s _ {2} = 3 0 0 \\ x _ {1} + x _ {2} + s _ {3} = 4 0 0 \\ x _ {1}, x _ {2}, s _ {1}, s _ {2}, s _ {3} \geq 0 \end{array}

The original was also in a useful form: maximize an objective subject to certain inequalities. Any LP can likewise be recast in this way, using the reductions given earlier.

Box: Matrix-vector notation

A linear function like $x _ { 1 } + 6 x _ { 2 }$ can be written as the dot product of two vectors

\mathbf {c} = \binom{1}{6} \text { and } \mathbf {x} = \binom{x _ {1}}{x _ {2}},

denoted $\mathbf { c } \cdot \mathbf { x }$ or $\mathbf { c } ^ { T } \mathbf { x } .$ Similarly, linear constraints can be compiled into matrix-vector form:

\begin{array}{r c l} x _ {1} & \leq & 2 0 0 \\ x _ {2} & \leq & 3 0 0 \\ x _ {1} + x _ {2} & \leq & 4 0 0 \end{array} \quad \Longrightarrow \quad \underbrace {\left( \begin{array}{c c} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{array} \right)} _ {\mathbf {A}} \quad \begin{array}{c c c} \left( \begin{array}{c} x _ {1} \\ x _ {2} \end{array} \right) & \leq & \underbrace {\left( \begin{array}{c} 2 0 0 \\ 3 0 0 \\ 4 0 0 \end{array} \right)} _ {\mathbf {b}}. \\ \mathbf {x} & \leq & \end{array}

Here each row of matrix A corresponds to one constraint: its dot product with x is at most the value in the corresponding row of b. In other words, if the rows of A are the vectors $\mathbf { a } _ { 1 } , \ldots , \mathbf { a } _ { m }$ , then the statement $\mathbf { A x } \leq$ b is equivalent to

\mathbf {a} _ {i} \cdot \mathbf {x} \leq b _ {i} \text { for all } i = 1, \dots , m.

With these notational conveniences, a generic LP can be expressed simply as

\begin{array}{c} \max \mathbf {c} ^ {T} \mathbf {x} \\ \mathbf {A x} \leq \mathbf {b} \\ \mathbf {x} \geq 0. \end{array}