An Algorithm for the Network Design Problem Based on the Maximum Entropy Method

摘要

Network design problem (NDP) is a well known NP-hard problem which involves topology selection (subset of possible links), routing determination (paths for the offered traffic) and possibly capacity assignment. The goal is to minimize the cost, which can be a combination of the link costs and delay penalties, under possible additional constraints. Network design and analysis almost always involve underdetennined systems, especially when routing policy has to be determined. The maximum entropy method (MEM) is a relatively new technique for solving underdetermined systems which has been successfully applied in many different areas. It is intuitively clear that an optimal network should not have overloaded or underutilized links. The maximum entropy constraint favors uniform distribution and gives a starting topology and routing with smoothly distributed traffic that is expected to be close to the optimal solution. We adjusted the network design problem, primarily the routing feasibility, to the maximum entropy method requirements. Computationally feasible algorithm is developed which implements the standard maximum entropy method, includes adjustments for problems that do not involve probabilities initially, calculates a function that substitutes large sparse matrix, includes heuristic that speeds up calculations by avoiding to invert Jacobian matrix at each iteration, determines variables that define constraints for the routing feasibility, includes additional constraints that direct uniformity of the solution in the desirable direction, cancels opposing traffic and excludes underutilized links. Mentioned additional constraints are "soft", which is a unique feature of this algorithm, in the sense that they do not have to be satisfied; the solution will be pulled in the direction of satisfying them as much as possible. Some theoretical results arc also established that direct initial approximation. Proposed algorithm computes a reasonable solution that is robust with respect to often required dynamic changes of the cost function. The maximum entropy solution can be a good starting point for further optimization considering that the cost function with delay penalties involves queuing theory that is usually computationally expensive.