Dual linear programming pdf

The black boxes The major problems with implementing the primal dual algorithm of Section 2 above are in Steps 2, 3,7 and 8. In particular, note that RFP is an integer program- ming problem that could be as difficult as the original problem P. Here, we discuss two approaches to dealing with solving RFP and implementing the black boxes of Steps 3 and 8 of the algorithm.

In Section 3. Then, in Section 3. Specifi- cally we specialize the results of Chvatal [5] to build dual superadditive functions using Gomory cutting planes in order to implement Steps 2, 3, 7 and 8 of the algo- rithm. Finally, in Section 3. In this case the cardinality matching algorithm of Edmonds [7] is used to solve RFP.

Easy special cases Here we briefly discuss two very special cases where implementation of the algo- rithm is easy. For any Jc 1,. First consider the case when PJ is feasible if and only if its linear programming relaxation is feasible for each J.

If so, then there is a linear function y the optimal dual solution to the linear programming relaxation of RFP that will satisfy the conditions of Step 3 of the algorithm. LleweNyn, J. Ryan function that occurs in Step 4 of the algorithm is vital to the convergence of the algorithm.

However in this case, because the linear dual solution can be used, con- vergence is guaranteed without rounding. Since no basis is ever repeated, the algorithm is finite. Thus, with the rounding step omitted, the dual function will remain linear throughout the execu- tion of the algorithm. As a consequence, complementary linearity will always be satisfied trivially, RMP need never be solved, and our algorithm reduces to the primal dual algorithm for linear programming. Next, define the group relaxation of P , called here G : max cx, s.

As our second easy special setting, we now consider the case when for any column set, J, the problem PJ is feasible if and only if both its linear relaxation and group relaxation are feasible.

A simple example where this condition holds is if A is a diagonal matrix with nonnegative integers along its diagonal. Now, to solve RFP one must first check if the linear relaxation is feasible. If not, then as above, the linear programming dual solution will work in Step 3 of the algorithm directly. If the linear relaxation is feasible, then next check the feasibility of the group relaxa- tion. Moreover, y can be found in polynomial time by a unimodular elimination scheme see [6].

This function satisfies the property required by Step 3 of the algorithm. If both the linear and group relaxations are feasible, then there is a feasible solution to RFP with value 0, and this solution will be optimal for P.

In particular, there will be an optimal solution to the linear programming relaxation of RFP that is integral. This integral solution can be found by pivoting among the alternate optima to the linear programming relaxation or by using other standard techniques.

Note that such an integral solution need only be sought in the final iteration of the algorithm. For any integer programming problem, the first instance of RFP to arise can always be easily solved in the absence of dual degeneracy in the linear programming relaxation.

In the absence of dual degeneracy the set J is exactly equal to the indices of the basic variables of the optimal solution of the linear programming relaxation. In [5] Chvatal has shown the following although using different terminology : Theorem 3. Theorem 3. Consider the restricted feasibility problem RFP. Similarly, consider the restricted maximization problem RMP. For continuity of exposition, the details of the construction of the function guaranteed by Theorem 3.

See also [20] for results relating cutting planes and Chvatal functions. Recall RFP , written as an optimization problem with artificial variables.

If the linear programming relaxation of RFP has an optimal solution with value less than 0, let y be the optimal dual solution. Otherwise, the optimal value of the linear programming relaxation of RFP is 0. That is, the following linear programming problem has value less than 0: s. If the optimal solution to RMP is less than f b , then let y be the optimal dual solution.

We now give the details of the construction of the function F corresponding to a cut as in Theorem 3. Although these can be derived from [5] we have included them for completeness. We will assume that we are working on RFP. The adapta- tion for RMP is straightforward: the same procedure is followed with the omission of the artificial variables. Let the slack variables which have been added to the tableau for the rows corre- sponding to the cuts be s,,.

Suppose that we want to cut on row i of the current tableau, and that row i has the form: where 6 is fractional. However adding 2 alone has the same effect, since 1 is an equality and remains part of the problem.

Note that the coefficients of the slacks in 1 will always occur in the ith row of B-I, since there were originally unit vectors in these columns.

Since yk- LykJ r0 always, F is a Chvatal function. They will remain valid. Moreover, when solving RMP , it is not necessary to continue to add cuts until the optimal integer solution is found. It suffices to add cuts only until the optimal fractional value falls below f b. Then the dual function f can be constructed as above, and it will have value less than f b as required by Step 8 of the algorithm. Of course, one must still construct this function from the facet defining inequality.

Matching The primal dual algorithm of Section 2 can be specialized to find a maximum weight matching in a weighted graph G. We have chosen this example because RFP can be solved efficiently. When it becomes necessary to solve RMP , deep cuts can be generated using a separation procedure due to Padberg and Rao [ This approach is not likely to be more efficient than specialized weighted matching algorithms, but provides a nice illustration of how the primal dual algorithm can be tailored to a specific problem.

Without loss of generality suppose that any maximum weight matching is a perfect matching G is easily altered so that this is the case. Let the node set of G be V. Given a graph G, an odd set cover of G is a set of node sets Nr,. Edmonds see [7] showed that the following duality holds: the maximum car- dinality of a matching in a graph is equal to the minimum capacity of an odd set cover.

The algorithm given in [7] returns both a maximum cardinality matching and the corresponding odd set cover. We will use this matching duality result here, and assume that we have available an algorithm that finds a maximum cardinality matching which also returns an odd set cover whose capacity is equal to the car- dinality of the matching. Problem RFP for the matching problem is efficiently solved.

Given J, we must determine if P is feasible using only the variables in J. In the matching setting, we must determine if there is a perfect matching in G using only the edges indexed by J. We begin by finding the maximum cardinality matching on the graph whose edges consist only of those indexed by J. If this is a perfect matching of G, then we have a feasible solution of P satisfying complementary slackness and we proceed to Step 6 or 7 of the algorithm. Otherwise, we have a matching of size p, where 2p is less than the number of nodes in G.

Without loss of generality assume that the vertices ur,. The function satisfies the condition of Step 3 in the algorithm. Now let e be an edge indexed by je J. Since e is indexed by a member of J, it is covered by the odd set cover given by the cardinality matching algorithm.

We now consider RMP. When we reach Step 7 of the algorithm we have found a perfect matching using only edges in J, but the value of that perfect matching is less than f b.

As discussed above, this can be accomplished by adding cutting planes until the value of RMP first drops below f b. Recall that RMP will always have value at most f b. In the matching setting we have the advantage that we know what the facets of the corresponding polytope are.

Let S be a set of nodes in the graph, and let E S denote the set of edges whose both endpoints are in S. Then every facet defining inequality is of the form where S is a node set of odd cardinality. It is easy to see that the function defines the facet derived from an odd set S. Now suppose that we have solved the linear programming relaxation of RMP , and obtained a basic fractional solution with value equal to f b. The fractional solution will violate one of the above facet describing inequalities.

Padberg and Rao [17] showed that the separation problem for the matching polytope can be solved in polynomial time. That is, a facet defining inequality that is violated by a given infeasible solution can be determined in polynomial time. Thus in polynomial time we can generate a cut as described above that will reduce the value of RMP as desired, or find an integer solution with value equal to f b. Future work Future work related to this algorithm shotrId be directed towards finding special structures which allow efficient solution of the restricted subproblems.

More specifi- cally, one aim is to identify cases where the problem can be solved without resorting to the use of cutting planes in the solution of RFP.

These problems can be of two types-those where the type of data is known to be such that the subproblems can be solved easily like those cases discussed in Section 3. With respect to this last type of problem, the richest potential lies with integer pro- gramming problems with known pseudopolynomial algorithms. One other direction for future work is in the area of column generation. A primal dual integer programming algorithm References [l] C.

Blair and R. Jeroslow, The value function of a mixed integer program 1, Discrete Math. Jeroslow, The value function of an integer program, Math.

Programming 23 Jeroslow, Computational complexity of some problems in parametric discrete programming I, Math. Burdet and E. Johnson, A subadditive approach to solve linear integer programs, in: Annals of Discrete Mathematics 1 North-Holland, Amsterdam, Chvatal, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math. Domich, R. Kannan and L. Trotter Jr, Hermite normal form computation using modulo determinant arithmetic, Math.

Edmonds, Paths, trees and flowers, Canad. Edmonds and F. Giles, A min-max relation for submodular functions on graphs, in: Annals of Discrete Mathematics 1 North-Holland, Amsterdam, Gomory, Outline of an algorithm for integer solutions to linear programs, Bull.

Gomory, Solving linear programs in integers, in: R. Bellman and M. Hall Jr, eds. Gomory, An algorithm for integer solutions to linear programs, in: R. Graves and P. Wolfe, eds. Gomory, An all-integer programming algorithm, in: J. Muth and G. Thompson, eds. Jeroslow, Cutting plane theory: algebraic methods, Discrete Math.

Johnson, Cyclic groups, cutting planes and shortest paths, in: T. Hu and S. Robinson, eds. Johnson, On the group problem and a subadditive approach to integer programming, in: An- nals of Discrete Mathematics 5 North-Holland, Amsterdam, l Consider 1 found in Step 9. Clearly by construction the numerator is positive. Thus, since a convex combination of Chvatal functions is a Chvatal function, pis a Chvatal function.

Now consider the flow of the algorithm. Notice that each time the algorithm leaves Step 2, it either ends up in Step 4, 5, 6, 8 or 9. Steps 5 and 6 are terminal steps as shown above. Further we have shown that when the algorithm leaves Steps 4, 8 or 9 to return to Step 2, it does so with an integral dual feasible function which forces the objective value to decrease by at least 1.

Thus if the subprob- lems can be solved in polynomial or pseudopolynomial time, a pseudopolynomial time algorithm results. We should note here that in Step 7, it is not necessary to solve RMP to optimali- ty. It is merely necessary to find a dual solution of value less thanf b which proves that the value of RMP is less thanf b.

Note that the dual of any linear program- ming solution of RMP will have value at mostf b. This fact results in computa- tional savings when Step 7 is implemented using cutting planes, as discussed in Section 3. The black boxes The major problems with implementing the primal dual algorithm of Section 2 above are in Steps 2, 3,7 and 8. In particular, note that RFP is an integer program- ming problem that could be as difficult as the original problem P.

Here, we discuss two approaches to dealing with solving RFP and implementing the black boxes of Steps 3 and 8 of the algorithm. In Section 3. Then, in Section 3. Specifi- cally we specialize the results of Chvatal [5] to build dual superadditive functions using Gomory cutting planes in order to implement Steps 2, 3, 7 and 8 of the algo- rithm. Finally, in Section 3. In this case the cardinality matching algorithm of Edmonds [7] is used to solve RFP.

Easy special cases Here we briefly discuss two very special cases where implementation of the algo- rithm is easy. For any Jc 1,. First consider the case when PJ is feasible if and only if its linear programming relaxation is feasible for each J.

If so, then there is a linear function y the optimal dual solution to the linear programming relaxation of RFP that will satisfy the conditions of Step 3 of the algorithm. LleweNyn, J. Ryan function that occurs in Step 4 of the algorithm is vital to the convergence of the algorithm. However in this case, because the linear dual solution can be used, con- vergence is guaranteed without rounding.

Since no basis is ever repeated, the algorithm is finite. Thus, with the rounding step omitted, the dual function will remain linear throughout the execu- tion of the algorithm.

As a consequence, complementary linearity will always be satisfied trivially, RMP need never be solved, and our algorithm reduces to the primal dual algorithm for linear programming. Next, define the group relaxation of P , called here G : max cx, s. As our second easy special setting, we now consider the case when for any column set, J, the problem PJ is feasible if and only if both its linear relaxation and group relaxation are feasible.

A simple example where this condition holds is if A is a diagonal matrix with nonnegative integers along its diagonal. Now, to solve RFP one must first check if the linear relaxation is feasible. If not, then as above, the linear programming dual solution will work in Step 3 of the algorithm directly. If the linear relaxation is feasible, then next check the feasibility of the group relaxa- tion.

Moreover, y can be found in polynomial time by a unimodular elimination scheme see [6]. This function satisfies the property required by Step 3 of the algorithm. If both the linear and group relaxations are feasible, then there is a feasible solution to RFP with value 0, and this solution will be optimal for P.

In particular, there will be an optimal solution to the linear programming relaxation of RFP that is integral. This integral solution can be found by pivoting among the alternate optima to the linear programming relaxation or by using other standard techniques. Note that such an integral solution need only be sought in the final iteration of the algorithm.

For any integer programming problem, the first instance of RFP to arise can always be easily solved in the absence of dual degeneracy in the linear programming relaxation. In the absence of dual degeneracy the set J is exactly equal to the indices of the basic variables of the optimal solution of the linear programming relaxation.

In [5] Chvatal has shown the following although using different terminology : Theorem 3. Theorem 3. Consider the restricted feasibility problem RFP. Similarly, consider the restricted maximization problem RMP.

For continuity of exposition, the details of the construction of the function guaranteed by Theorem 3. See also [20] for results relating cutting planes and Chvatal functions. Recall RFP , written as an optimization problem with artificial variables. If the linear programming relaxation of RFP has an optimal solution with value less than 0, let y be the optimal dual solution. Otherwise, the optimal value of the linear programming relaxation of RFP is 0.

That is, the following linear programming problem has value less than 0: s. If the optimal solution to RMP is less than f b , then let y be the optimal dual solution.

We now give the details of the construction of the function F corresponding to a cut as in Theorem 3. Although these can be derived from [5] we have included them for completeness. We will assume that we are working on RFP. The adapta- tion for RMP is straightforward: the same procedure is followed with the omission of the artificial variables. Let the slack variables which have been added to the tableau for the rows corre- sponding to the cuts be s,,.

Suppose that we want to cut on row i of the current tableau, and that row i has the form: where 6 is fractional. However adding 2 alone has the same effect, since 1 is an equality and remains part of the problem. Note that the coefficients of the slacks in 1 will always occur in the ith row of B-I, since there were originally unit vectors in these columns.

Since yk- LykJ r0 always, F is a Chvatal function. They will remain valid. Moreover, when solving RMP , it is not necessary to continue to add cuts until the optimal integer solution is found. It suffices to add cuts only until the optimal fractional value falls below f b. Then the dual function f can be constructed as above, and it will have value less than f b as required by Step 8 of the algorithm. Of course, one must still construct this function from the facet defining inequality.

Matching The primal dual algorithm of Section 2 can be specialized to find a maximum weight matching in a weighted graph G. We have chosen this example because RFP can be solved efficiently. When it becomes necessary to solve RMP , deep cuts can be generated using a separation procedure due to Padberg and Rao [ This approach is not likely to be more efficient than specialized weighted matching algorithms, but provides a nice illustration of how the primal dual algorithm can be tailored to a specific problem.

Without loss of generality suppose that any maximum weight matching is a perfect matching G is easily altered so that this is the case. Let the node set of G be V. Given a graph G, an odd set cover of G is a set of node sets Nr,. Edmonds see [7] showed that the following duality holds: the maximum car- dinality of a matching in a graph is equal to the minimum capacity of an odd set cover.

The algorithm given in [7] returns both a maximum cardinality matching and the corresponding odd set cover. We will use this matching duality result here, and assume that we have available an algorithm that finds a maximum cardinality matching which also returns an odd set cover whose capacity is equal to the car- dinality of the matching.

Problem RFP for the matching problem is efficiently solved. Given J, we must determine if P is feasible using only the variables in J. In the matching setting, we must determine if there is a perfect matching in G using only the edges indexed by J. We begin by finding the maximum cardinality matching on the graph whose edges consist only of those indexed by J. If this is a perfect matching of G, then we have a feasible solution of P satisfying complementary slackness and we proceed to Step 6 or 7 of the algorithm.

Otherwise, we have a matching of size p, where 2p is less than the number of nodes in G. Without loss of generality assume that the vertices ur,. The function satisfies the condition of Step 3 in the algorithm.

Now let e be an edge indexed by je J. Since e is indexed by a member of J, it is covered by the odd set cover given by the cardinality matching algorithm. We now consider RMP. When we reach Step 7 of the algorithm we have found a perfect matching using only edges in J, but the value of that perfect matching is less than f b.

As discussed above, this can be accomplished by adding cutting planes until the value of RMP first drops below f b. Recall that RMP will always have value at most f b. In the matching setting we have the advantage that we know what the facets of the corresponding polytope are. Let S be a set of nodes in the graph, and let E S denote the set of edges whose both endpoints are in S. Then every facet defining inequality is of the form where S is a node set of odd cardinality.

It is easy to see that the function defines the facet derived from an odd set S. Now suppose that we have solved the linear programming relaxation of RMP , and obtained a basic fractional solution with value equal to f b. The fractional solution will violate one of the above facet describing inequalities.

Padberg and Rao [17] showed that the separation problem for the matching polytope can be solved in polynomial time. That is, a facet defining inequality that is violated by a given infeasible solution can be determined in polynomial time.

Thus in polynomial time we can generate a cut as described above that will reduce the value of RMP as desired, or find an integer solution with value equal to f b. Future work Future work related to this algorithm shotrId be directed towards finding special structures which allow efficient solution of the restricted subproblems. More specifi- cally, one aim is to identify cases where the problem can be solved without resorting to the use of cutting planes in the solution of RFP.

These problems can be of two types-those where the type of data is known to be such that the subproblems can be solved easily like those cases discussed in Section 3. With respect to this last type of problem, the richest potential lies with integer pro- gramming problems with known pseudopolynomial algorithms. One other direction for future work is in the area of column generation. A primal dual integer programming algorithm References [l] C. Blair and R. Jeroslow, The value function of a mixed integer program 1, Discrete Math.

Jeroslow, The value function of an integer program, Math. Programming 23 Jeroslow, Computational complexity of some problems in parametric discrete programming I, Math.

Burdet and E. Johnson, A subadditive approach to solve linear integer programs, in: Annals of Discrete Mathematics 1 North-Holland, Amsterdam, Chvatal, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math. Domich, R. Kannan and L. Trotter Jr, Hermite normal form computation using modulo determinant arithmetic, Math.

Edmonds, Paths, trees and flowers, Canad. Edmonds and F. Giles, A min-max relation for submodular functions on graphs, in: Annals of Discrete Mathematics 1 North-Holland, Amsterdam, Gomory, Outline of an algorithm for integer solutions to linear programs, Bull.

Gomory, Solving linear programs in integers, in: R. Bellman and M.