Tuesday, June 14, 2005

LP Duality and Darte's decomposed Software Pipelining

A paper by Darte and others on decomposed SWP finally ends with a LP program. They claim that the constraint matrix of that particular LP program is totally unimodular, and so the feasible solutions to that problem are integral, not just rational. The constraint matrix looks dangerously similar to the constraint matrix of the following problem encountered in a linear programming course (Refer Chong's textbook/lecture notes-17):

Given a LP program in standard form, frame a new LP program that has both the primal and dual variables of the original program as its variables. Or, write a LP program whose feasibilty conditions are exactly of those of the original LP program and also of the dual of the original LP program.
Schrijver's book says: if the constraint matrix is total-unimodular, then all the points on the surface of the defined polyhedron are integral. This means that the solution is an integer point, not just a rational one. This also corresponds to the set of problems which are in the set NP \cap co-NP. So, a polynomial time algorithm is possible for those problems. (It can also be said that the same is true for all problems in NP, but it means assuming something, which may be possibly presumptous.:)
So, given a usual graph theoretic flow problem, which can be formulated as a LP program, do the following to know if the problem is nice:
"reason about the feasibility of the primal and dual and the constraint matrices of both. If they turn out to be total-unimodular, then the program has integer solutions and the problem is in NP \cap co-NP". Then think hard and write a graph theoretic algorithm to solve the problem.
Note: in such constraint matrices, we usually deal with the incidence matrix, not the adjacency matrix.
Question: We know now know that LP is in P, using any of Khachiyan, Karmarkar, Karp. Then, how much of the above is new?

No comments: