A Resource Allocation Approach for the Generation of Service-Dependent Demand Matrices for Communications Networks

Estimating point-to-point demands from partially available information, such as total demand volumes originating and terminating at nodes and traffic volumes routed on links, has significant applications in various areas, such as communications network planning and transportation planning. Existing methods include matrix and link scaling methods, statistical methods, more complex mathematical programming models, and forecasting using demographic data. We present a new mathematical programming model based on equitable resource allocation. The model considers multiple services, e.g., data, video, and voice, and generates a point-to-point demand matrix for each service. Originating and terminating demands for each service and link loads, aggregated over all services, are viewed as resources. Each point-to-point demand is associated with a performance function that measures its weighted, normalized deviation from a target defined by a service-dependent community of interest matrix. The model formulation has a lexicographic minimax objective function and multiple knapsack resource constraints. The model has an intuitively appealing interpretation and a specialized algorithm can generate demand matrices for large network problems very fast.     

A hierarchical strategy for solving traveling salesman problems using elastic nets

In this article, we focus on implementing the elastic net method to solve the traveling salesman problem using a hierarchical approach. The result is a significant speed-up, which is studied both analytically and experimentally.