Operations Research

e-Notes	Topic	Subject Experts
Unit 1	Linear Programming-Introduction	Prof. N. S. Narahari, RVCE, B'lore
Unit 2	Linear Programming	Prof. G.Rajendra, Dr.AIT, B'lore
Unit 4	Assignment Problem
Unit 3	Transportation Problem	Dr.S.V.Prakash, MSRIT, B'lore.
Unit 5	Queuing Theory	Dr.N.V.R.Naidu,MSRIT. B'lore
Unit 7	Replacement Analysis
Unit 6	Project Management Using Network Analysis	Dr. G N Mohanbabu, MSRIT, B'lore
Unit 8	Game Theory	Prof. N. S. Narahari, RVCE, B'lore

Upper Bounds on Integer Programs

Probably the most important fact concerning linear programming techniques and their relationship to integer programming problems is:

The relaxed (or linear programming) solution to an integer programming problem is an upper bound for all feasible integer solutions.

With this in mind, examine the optimization problem pictured in the shaded area of figure 1a.

Figure 1 - Bounding Example

If the objective function for this problem is z = x₁ + x₂, the optimum solution found by linear programming is the pair:

< x₁ , x₂> = <6.5, 7.5>

and due to the above observation, we know that no integer solution can produce a higher value for the objective function than this solution.

Now suppose we were to break the problem into two subproblems, one where x₁ is restricted to values no less than 7 and one where x₁ is restricted to values no greater than 6. This is easily done by adding constraints (namely: x₁ ³ 7 and x₁ £ 6) to the original collection. These subproblems are pictured as the shaded areas of figure 1b. Note particularly that no feasible integer solutions have been omitted as they are all in one of the two shaded areas. Only the vertical strip of noninteger space between 6 and 7 has been removed. Relaxing these two new problems and solving for optima provides us with the solutions for our new problems that appear below.

<6, 6.5> and <7, 6.5>

as solutions to the two subproblems. This is closer to the kind of solution we wish, but it still is not an integer solution.

Subdividing these two problems results in three new problems that are shown as the shaded areas of Figure 1c. This time we removed horizontal strips from the solution space.

Continuing on, we divide the remaining problems as indicated by the tree in Figure 2. It shows all of the subproblems and the optimum solutions for each.

Figure 2 - Solution Search Tree

One more subdivision took place after that shown in Figure 1c. The shaded region to the right was split into two subproblems. By restricting x₁ to be no greater than 7, we get as a feasible solution space, a line with an x₁ value of 7 and x₂ ranging from 2 to 6. By restricting x₁ to be no less than 8 we end up with an area containing the single point <8, 4.75>.

At this stage in the process three integer solutions have been found and one mixed solution still remains. The integer solutions all set the objective function to 13 and this is better than the remaining mixed solution <8, 4.75>. Thus any of the three is the optimum and we need not pursue the path in the search tree below the mixed solution.

In figure 3 the algorithm for this method is provided.

Figure 3 - A Bounding Algorithm for Integer Programming

A final note on this method is in order. This algorithm seems to have a slight advantage over the cutting plane method because the problem involves a smaller solution space at each stage. And, if we are fairly clever, some of the constraints in the original problem can be removed if the new bounding constraint supercedes them. For example, in figure 1a we solved a problem with four constraints, while in figure 1b there were two problems, each with three constraints. And since we are always splitting the problem at a vertex of its feasible solution space, at least one constraint can disappear from the new problem at each stage.

Cutting Plane Techniques

We have found a large class of problems, which can be stated conveniently as integer programming problems. We have also discovered that a large subclass of this cannot be solved by straight linear programming techniques. Thus we need to look further for ways to solve integer programming problems.

Previously we mentioned the idea of solving our integer programs with linear programming methods. Removing the constraint, which requires integer solutions, is called the relaxation of the integer programming problem. Solving this relaxed problem always brings an optimum solution, but as we have seen, rounding off this solution often does not always provide the optimum integer solution. We do know however that:

The optimum solution to the relaxation of an integer programming problem is an upper bound for the optimum integer solution

Consider the following example. Figure 1a shows a convex region of feasible solutions defined by several constraints. The grid indicates where inside the polygon the feasible integer solutions lie. The dot represents the optimal solution (for the linear programming problem) gained from maximizing x₁ + x₂. Note that although it is not an integer solution it is the upper bound for an optimum one.

Figure 1 - Cutting Plane Example

If we could shave off some of the area, which contains noninteger solutions, we could possibly find an optimal integer solution. Examine the vertical line through x₁ = 3 in figure 1a. Cutting the polygon on this line will not destroy any feasible integer solutions to the problem. In figure 1b we have done this and have a new polygon.

The line we used to shave off part of the polygon is called a cut or a cutting plane since it pares off some of the noninteger area we do not care about. And, to do the carving, all we need do is to introduce this cut as an additional constraint. Note that no feasible integer solutions were omitted by including this new constraining line in out linear programming problem.

The dot in figure 1b again represents the optimum solution we get from solving the relaxation. In figure 1c we have added yet another constraint and finally arrive at an optimum integer solution.

This seems like a good idea. All we need do is solve the relaxation of the integer programming problem and generate additional constraints until we get an integer solution. During this process we would like to guarantee that as we add constraints:

a) No feasible integer solutions are excluded.
b) Each constraint reduces the feasible solution region.
c) Each constraint passes through an integer point.
d) An optimum solution is eventually found.

Let's go straight to an example. In figure 2a we have the linear programming problem specified by

maximize z = x₁ + x₂
subject to the constraints:
-5x₁ + 4x₂ £ 0
5x₁ + 2x₂ £ 15
where all x_i ³ 0.

Figure 2 - Cutting Plane Application

Solving the relaxation of the integer program gives us the optimum solution indicated by the dot at the top of the triangle in figure 2a. The values for the variables in this feasible solution are:

x1	x2	y1	y2
2	5/2	0	0

and the final tableau after solving for this solution is:

x1

x2

y1

y2

bi

0	0	-1/10	-3/10	-9/2	-z
0	1	1/6	1/6	5/2	x2
1	0	-1/15	-1/15	2	x1

In the second row of the tableau there is a noninteger value for the variable x₂. In this row we find the equation:

Let us leave the fractional portions of our variables on the left hand side of the equation and move x₂ to the right. If we separate the right side into integer and fraction portions, we get the following.

Let us examine this equation. Suppose that all of the variables were set to their optimum integer solutions. Since we do not allow negative solutions, the left hand side of the equation must be greater than zero. This means that the right hand side of the equation cannot be negative either. Thus:

This in turn forces the quantity (x₂ - 2) to be no more than 1/2. Since the value of x₂ must be a nonnegative integer, x₂ can only be zero, one or two. This means that the left side of the equation above will always have a value of more than 1/2. Putting this all together we assert that if x₂ is to have an integer value then the following holds.

This is a necessary (but not sufficient) condition for optimum integer values for the variables. Adding this condition to our collection of constraints (along with its surplus variable y₃) at this point in the solution has the same effect as beginning with the additional constraint x₂ £ 2. This cuts off the area above 2 for x₂ and gives us the polygon in figure 2b and the following tableau for our linear programming problem.

x1

x2

y1

y2

y3

bi

0	0	-1/10	-3/10	0	-9/2	-z
0	1	1/6	1/6	0	5/2	x2
1	0	-1/15	-1/15	0	2	x1
0	0	1/6	1/6	-1	1/2

We are now one column shy of a basis and must remedy that immediately. Examination of the tableau reveals that y₃ cannot enter the basis, but both y₁ and y₂ might if so desired. We may select either. We choose to pivot on the bottom row and place y₁ into the basis. This results in the tableau:

x1

x2

y1

y2

y3

bi

0	0	0	-1/5	-4/5	-21/5	-z
0	1	0	0	1	2	x2
1	0	0	1/5	-2/5	11/5	x1
0	0	1	1	-6	3	y1

Again we have an optimum feasible solution. This one is indicated by the dot on the picture in figure 2b and corresponds to:

x1	x2	y1	y2	y3
11/5	2	3	0	0

As before, we select the row that provided a noninteger solution, this time involving x₁. This gives us the equation:

We wish to do as before and end up with positive fractions on the left hand side so that it will be greater than zero. To do this, we just add y₃ to both sides. Then we transform the equation into:

by moving the integer portions of x₁ and y₃ to the right. Now we group the integer portions of the right hand side together and get:

by moving x₁ and y₃ to the right and group the integer portions of that side. Again we see that the left side must be positive. Thus the right side must be positive and by employing similar arguments to those used above, we may assert that the following holds.

Adding this new cutting plane restricts our solution to values of x₁ below two. So, we add the new cutting plane to the collection of constraints and pivot. Again we need one more variable in the basis and this time we chose y₂. This leads to the final tableau:

x1

x2

y1

y2

y3

y4

bi

0	0	0	0	-3/5	-1	-4	-z
0	1	0	0	1	0	2	x2
1	0	0	0	-1	1	2	x1
0	0	1	0	-9	5	2	y1
0	0	0	1	3	-5	1	y2

with the optimum integer solution given below and shown in figure 2c.

x1	x2	y1	y2	y3	y4
2	2	2	1	0	0

A recapitulation is in order. First we relax the integer programming problem and solve for the optimum solution with linear programming methods. If we achieve an integer solution, then of course we are finished. If not, then there is a row of the tableau such as:

where b is not an integer. We then split b and all of the a_i into integer and nonnegative fractional parts. (The integer portion of b is written b^I and its fractional part is b^F.) Now the equation is rearranged so that it looks like this:

We now consider the case where all of the variables are set to their optimum integer values (which must of course be nonnegative), and deduce several things from the above equation. If the fractional portions of all the a_i are nonnegative, then we know that both sides of the equation are no less than zero. Thus

since it has an integer value and is not less than -b^F. This in turn makes

If we add the above fractional equation to the collection of constraints in the tableau, it is the same as if we began with the previous integer equation as an initial condition. This is the essence of the cutting plane method of solving integer linear programming problems. It makes linear programming problems larger and larger as new constraints are added.

We merely iterate this process and hope for integer solutions to appear quickly. But, there are several problems. First, the tableaux can become very large indeed. Often though this is avoided by dropping slack variables introduced with cutting planes whenever they enter the basis.

A second problem enters because we are using computers to solve our linear programming equations and computers have finite precision. Thus, noninteger solutions (such as 5.99999999) might be difficult to detect. Employing algorithms in which coefficients remain integers does solve this. For example, save the numerator and denominator of fractions. But, this adds to the execution time.

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.