LP-based algorithm for optimization in multiservice IP networks

The network design problem considered in this paper provides the basis for the solution of many interesting and practical engineering problems, of which one notable example is the link capacity expansion problem of existing communication networks. We are particularly interested in the possibility of using this problem as a subproblem when solving the planning and design problem of multiservice IP networks (e.g., DiffServ/MPLS). After discussing its application as part of a solution method for multiservice IP network planning problem, an integer multicommodity optimization problem is formulated. For its solution an LP-based algorithm was developed, that uses the optimization tool ILOGTM CPLEX7:1 LP for finding the exact optimal solution of the considered problem. Computational tests on problems of various sizes lead to the conclusion that the algorithm is quite powerful both with respect to problem size and solution time