Given a communication network modeled as a graph G with each link in the graph associated with two nonnegative weights, cost and delay, we consider the problem of selecting a set of k link disjoint paths from a node s to another node t such that the total cost of the paths is minimum and the total delay of these paths is not greater than a specified bound A. This problem to be called the CSDP(k) problem can be formulated as an ILP problem. Relaxing the integrality constraints results in an upper bounded LP problem. We study the relaxed problem using the Revised Simplex Method. We discuss different issues such as formulas to identify entering and leaving variables, anti-cycling strategy, data structure for basis graph representation etc., related to an efficient implementation of our approach. We show how to extract from an optimal solution to the relaxed LP problem a set of k link disjoint s-t paths which is an approximate solution to the original CSDP(k) problem. We present several theoretical results that are also of general result in network optimization. We present simulation results that demonstrate that our algorithm is faster than currently available approaches.
展开▼
