Transition to Integer Solutions

One interesting circumstance from the last section is the following observation. Since we traveled the edges of the polytope formed by intersecting the constraints of our linear programming problems, we often came upon integer solutions to our problems. And, in problems where integer solutions are necessary (such as bipartite graph matching), we found them. Let us explore this further.

Consider minimal spanning trees for weighted graphs. This problem is never solved as a linear programming problem, but can be easily stated as one. Recall that we want to find a minimum weight collection of edges that connect all of the graph's vertices. That is the minimum spanning tree for the graph. Figure 1a contains a small graph whose minimum spanning tree is the pair of edges: {<a, b>, <b, c>}.

Figure 1 - A Minimal Spanning Tree and an Integer Program

To express the minimum spanning tree problem for this graph as a linear programming problem, we need to state some conditions. We begin by assigning a variable to each edge of the graph. (For example, x_ab represents the edge from node a to node b.) If a variable takes the value one, then that edge is in the minimum spanning tree. Thus the tree consisting of {<a, b>, <b, c>} would be defined by setting x_ac to zero and both x_ab and x_bc to one.

The first constraint of figure 1b calls for two edges in the tree and the others require the variables to take values between zero and one. (In other words, no more than two edges may be in the tree and each edge can be in it at most once.)

The shaded region of Figure 1c is the polytope formed by the intersection of all of the constraints. The constraints that limit the variables to values between zero and one define a unit cube and the first constraint slices the cube on a diagonal. This shaded triangular plane contains all of the feasible solutions to the problem. Note that some of the solutions call for portions of the edges to be in the spanning tree. (For example, two-thirds of each edge is a feasible solution!) And especially note that the vertices of this region are the three integer solutions to our problem. This means that when we minimize the sum of the variables times the weight of their edges, we will indeed get the proper solution since the vertices of the polytope defined by the constraints are basic feasible solutions.

After placing the constraints in standard form we find that the complete linear programming problem statement for the minimum spanning tree of the small graph in figure 1a is:

minimize z = 2x_ab + 7x_ac + 3 x_bc
subject to the constraints:
x_ab + x_ac + x_bc = 2
x_ab + y₁ = 1
x_ac + y₂ = 1
x_bc + y₃ = 1
where x_ab, x_ac, x_bc ³ 0

Since there is no feasible solution at the origin, we of course would have to apply the two-phase process to extract a solution. (We must also note that Gaussian elimination is far more time consuming than any of the standard methods for building a minimum spanning tree.)

Going on to larger problems, we must do a bit more than require that two of three edges be in the spanning tree. Figure 2 contains a slightly larger graph whose minimum spanning tree is:

{<a, c>, <a, e>, <b, c>, <b, d>, <c, f>}

Let us develop the constraints for this problem. As before, we assign a variable to each edge of the graph, and, if the variable x_uv is 1 then the edge from node u to node v is in the tree. To find the minimum spanning tree we again minimize the sum of the variable-weight products. And, once more, we require the variables to have values between zero and one.

Figure 2 - A Weighted Graph

To achieve a spanning tree we require that exactly 5 edges are in the tree, it spans the vertices, and there are no cycles. To ensure that exactly 5 edges are placed in the tree, we state:

x_ab + x_ac + x_ae + x_bc + x_bd + x_cd + x_ce + x_cf + x_df + x_ef = 5

With just the above constraint, one could select the five smallest edges and have a feasible solution. This, however, would not span the graph. Making sure that the tree spans the graph means insisting that for every node, one of the edges connected to it must be in the tree. This requirement induces the following constraints:

xab + xac + xae ³ 1	[vertex a]
xab + xbc + xbd ³ 1	[vertex b]
xac + xbc + xcd + xce + xcf ³ 1	[vertex c]
xbd + xcd + xdf ³ 1	[vertex d]
xae + xce + xef ³ 1	[vertex e]
xcf + xdf + xef ³ 1	[vertex f]

Keeping cycles from appearing is done by taking all subgraphs in which it is possible to have a cycle and bounding the edges, which may be included in the spanning tree. For example, the subgraph containing the nodes {a, b, c} might have a cycle of length three, so we write:

x_ab + x_ac + x_bc £ 2

and for the subgraph containing {a, b, c, d} we include:

x_ab + x_ac + x_bc + x_bd + x_cd £ 3

Completing the collection of anti-cycle conditions such as those above completes the description of the minimum spanning tree.

As before, we get an integer valued answer when we apply the simplex method. This is again because the vertices of the polytope defined by the constraints have values of zero and one for all variables.

There is one problem though. There are about 26 constraints needed for cycle prevention in the last graph and it was not a very large graph. And, since it was planar, it did not have many edges. To find the minimum spanning tree for an arbitrary graph we might need a great many constraints. In fact, it is possible in some problems to have an exponential number of constraints. This is why we do not solve these problems with linear programming methods.

A much easier problem to define in linear programming terms is the NP-complete knapsack problem. Recall that in this problem we have n objects, and the i-th one weighs w_i and has a value of v_i. We wish to pack a knapsack of capacity K with a valuable collection of objects. Our variable set shall be {x₁, x₂, … , x_n}, and we set the variable x_i to 1 when the i-th object is in the knapsack. Maximizing the value held in the knapsack is done by the following objective function.

We also require that all variables are greater than zero (x_i ³ 0) and bound the knapsack weight with the constraint:

This seems to work quite well and is easy to express. And, in fact, we may easily look at a small example example. Let us consider a problem with only two objects so that we can draw the polytope of feasible solutions. Let one object weigh 5 pounds and the other weigh 8 pounds. Also, let them have values of 1 and 2. If we wish to pack a knapsack of capacity 23, the problem can be very simply stated in linear programming terms as indicated in figure 3.

 

Figure 3 - A Simple Knapsack Problem

The picture in figure 3 provides the feasible solution space for this problem. We see that applying linear programming to this problem will provide a correct optimum feasible solution of x₁ = 0 and x₂ = 23/8. This would be fine if the objects were liquid or if we could chop them up. In those cases one merely fills the knapsack with pieces of the object which has the largest value per pound.

But, we want to place whole objects in the knapsack! The solution we are looking for is x₁ = 1 and x₂ = 2. Linear programming comes close to the solution, but does not provide it. This is because we must have integer solutions and that is a nonlinear constraint. In fact, the feasible integer solution space is the collection of grid points that are in the shaded area of the graph. This is not a convex space. So, it seems that knapsack is not so easy to solve after all.

Now consider the closed city tour problem. Recall that there are n cities with costs c_ab (to travel from city a to city b) and we wish to make a minimum cost closed tour (a loop) of the cities visiting each city exactly once. As before, we shall assign one variable to each edge of the graph of cities. Thus variable x_ab = 1 indicates that we have traveled from city a to city b on the tour. We must keep the variables at values of zero or one and ensure that we leave and enter each city exactly once. In integer linear programming form this becomes:

subject to the constraints:

x_ij Î {0,1} for all i, ,j

But things are not that simple. A collection of regional tours (as shown in figure 4a) connecting all of the cities meets the conditions set forth above. To eliminate these regional tours, we must have additional constraints. We note that for every subset of cities, part of the tour must lead into and part must lead out of the subset. This is illustrated in figure 4b.

Figure 4 - Closed Tour Considerations

Elimination of local subtours in some subset S of the n cities is done by specifying a constraint which requires entering or leaving the subset. These constraints are of the form:

for every proper subset of cities S. This does take care of the regional tour problem, but introduces a number of additional constraints equal to the number of subsets of the n cities. Unfortunately, this is exponential in the number of cities.

Getting out of this constraint explosion can be done placing an order upon visits to cities. First, mandate that the tour must begin with city 1. Then assign a variable t_i to each city to indicate the city’s place on the tour. (That is, if t_i = 17 then city i is the seventeenth city on the tour.) In order to insure that:

1. All cities are between 2^nd and n-th on the tour, and


2. Cities adjacent on the tour have consecutively numbered places on the tour,

we set t₁ to 1, and for all i ¹ k between 2 and n, we include the constraint:

t_i - t_k + nx_ik £ n -1

and note that if x_ik = 1, then t_k must be greater than t_i. That is, city i must precede city j on the tour. It also follows that any city that comes after city i on the tour has a larger t-value than t_i. Since the above inequality also requires each of these values is less than n, we may rest assured that we have a proper tour.

This is fine since we have a suitable number of constraints for the problem. So, why not solve it with linear programming methods and achieve an answer in polynomial time? Because the same problem we ran into with the knapsack problem arises, namely that the polytope in question does not have all integer vertices. We might get solutions with cities visited in places 17.35 or 24.7 on the tour and this of course is not acceptable.

(One solution to this problem is to use constraints such as:

x_ik *(t_i - t_k) = 1

but this is no longer a linear relationship and so we cannot use linear programming to solve it.)

There is of course the possibility that a feasible solution found through linear programming is close to the optimum integer solution. But this is not always the case since we could in fact have rather nasty polytopes for some problems. Consider those pictured in Figure 5.

Figure 5 - Non Integer Optimum Solutions

The feasible solution spaces are the shaded areas and if we maximize z = x₁ + 2x₂ in both of these cases, the optimum integer solutions (the dots) are nowhere near the best feasible solutions found by linear programming. Thus we cannot even round the best solution off to the closest integer and be assured of the correct answer. We need other methods to solve these systems since as we mentioned above, requiring answers to take on integer values is a nonlinear constraint.

This is not a complete disaster though. If we can express a problem in integer programming terms and have some method of solving integer programs, then we have achieved our goal. Let us concentrate upon the class to which the Knapsack problem and the Closed Tour problem belong; the class of NP-complete problems.

Since 0-1 integer programming is NP-complete, we know that all of the problems in NP can be expressed as integer programs. In particular, we know how express the satisfiability problem as an integer program. This means that expressing a problem in propositional calculus leads to an integer programming representation of the problem. In the proof where satisfiability is reduced to integer programming, clauses were changed to equations almost immediately and the constants on the right hand sides of the equations were set to one more than the number of negative literals in the clause. For example:

Setting all of the x_i £ 1 completes the development of the linear program. In order to solve the problem we execute phase one of the linear programming algorithm, and immediately find a feasible solution. In the case above, we get a solution that contains values of zero and one for all of the variables. This is exactly as we wished! But, we are not always so fortunate. In Figure 6 is a very simple satisfiability problem with the first basic feasible solution at <0.5, 0.5, 0.5>.

But sometimes one is fortunate, and often a linear programming solution to an integer programming problem leads to a reasonable approximation to the original problem. For this reason we shall explore techniques for defining problems in terms of propositional calculus.

Figure 6 - Non Integer Satisfiability Polytope

Sometimes it helps express a problem in integer programming terms if we can first express it as a set of formulas in the propositional calculus. For example, consider graph coloring. Recall that this problem requires one to color the vertices of a graph so that adjacent vertices do not share a color. The graph of figure 2 can be colored in this manner with four colors, but not with three.

To express this as an optimization problem we shall introduce the family of variables x_uk which represent node u being colored with color k. Then for each edge <u, v> in the graph we state that both u and v cannot be the same color. This is stated as the collection of clauses:

where each merely states that either u or v must not be color k. Each of these translates into the constraint:

x_uk + x_vk £ 1

for each edge <u, v> and color k. To make sure that each vertex is colored, we add the clause:

(x_u1 , ... , x_un)

which states that u is indeed one of the colors. This is translated into the constraint:

which if we are not careful will allow vertex u to be colored with several colors. We shall fix this later though.

Let's pause a moment. The constraints which state that adjacent nodes should not be the same color can be pooled if there are cliques in the graph. Finding cliques is not often cost effective, except for small ones (size 3 or 4). In the graph of figure 2 we pool cliques and get the following constraints for each color k:

x_ak + x_bk + x_ck £ 1
x_ak + x_ck + x_ek £ 1
x_ck + x_ck + x_fk £ 1
x_ck + x_dk + x_fk £ 1
x_bk + x_ck + x_dk £ 1

Note that each equation merely states that color k is used for at most one of the vertices in the clique.

The optimization portion of this problem requires some care since we wish to use the minimum number of colors. If we weight each color, then we can favor the first colors enough so that new colors are never introduced unless needed. We can think of this in terms of cost. For example charge $1 for each vertex that is color one, $n for each color two vertex, $n² for each that is color three, and so forth. Thus minimum cost means that we should use lower numbered colors on the vertices of the graph. The objective function is the following.

This makes using an additional colors very expensive.

One of the important things we discovered in this section was that when polynomially computable problems are expressed as linear programs, the solutions often emerge as integers. But when NP-complete problems are expressed as linear programming problems, basic feasible solutions often are not integers. Recalling a little matrix algebra helps explain this phenomenon.

Our basic feasible solutions come from a set of m unit vectors which appear as columns during execution of the simplex algorithm. If we denote the original m linearly independent columns which make up this basis as the matrix B then we may state that Bx = b. And, solving for the values of x we get:

in terms of the adjoint of B (B^adj) and B's determinant. This ties in with the next two definitions.

Definition. A square, integer matrix is unimodular if its determinant has the value ± 1.

Definition. An integer matrix is totally unimodular if all of its square, nonsingular submatrices are unimodular.

Now at last things fall into place a little. Linear programming problems that can be stated in totally unimodular form will indeed have integer feasible solutions since the denominator of the above formula will be one. It conveniently turns out that path problems, flow problems, and matching problems in networks and graphs have this property. Therefor, they can be solved with linear programming, but NP-complete problems cannot. We need some different methods for these.