Real Time Scheduling and Routing: Using Column Generation, Branch-and- Cut, and Modern Heuristics to Solve Difficult Combinatorial Optimizational Problems

摘要

The objective of the bandwidth-packing problem is to decide which demands, or calls, on a list of requests should be chose to route on a capacitated network. The objective is to maximize the revenue that is obtained by routing the chosen calls. If call splitting is allowed, then a multi- commodity flow formulation can be used. However, we are concerned with the situation where call splitting is not allowed, as with video data. Without call splitting, the problem requires that one know the paths upon which the calls are routed. There are many possible paths for each call. Oox et al 1991, Laguna and Clover 1993, Anderson, Jones, Parker and Ryan 1993, Parker and Ryan 1994, and Kang and Park 1996 have done research on this problem. A number of problems exist within the open literature as the common test bed. This problem is of interest to the US Navy as part of a larger project known as the Network Centric Warfare (NSW). NSW is concerned with applying advanced communications technology to achieve improved military effectiveness while simultaneously avoiding the expense of building large numbers of new weapon systems and platforms. Within this framework, the Navy has devoted considerable attention to nodal targeting-- an offensive form of NOW. Here, the aim is to identify a select set of nodes critical to an enemy network and attack these nodes in the hopes of crippling the entire system. In short, it is the study of conducting precision engagement to reduce effectiveness of the enemy.