Real Time Scheduling And Routing Using Column Generation Branch And Cut And Modern Heuristics To Solve Difficult Combinatorial Optimizational Problems

Column Generation

Column Generation is an insightful overview of the state of the art in integer programming column generation and its many applications. The volume begins with "A Primer in Column Generation" which outlines the theory and ideas necessary to solve large-scale practical problems, illustrated with a variety of examples. Other chapters follow this introduction on "Shortest Path Problems with Resource Constraints," "Vehicle Routing Problem with Time Window," "Branch-and-Price Heuristics," "Cutting Stock Problems," each dealing with methodological aspects of the field. Three chapters deal with transportation applications: "Large-scale Models in the Airline Industry," "Robust Inventory Ship Routing by Column Generation," and "Ship Scheduling with Recurring Visits and Visit Separation Requirements." Production is the focus of another three chapters: "Combining Column Generation and Lagrangian Relaxation," "Dantzig-Wolfe Decomposition for Job Shop Scheduling," and "Applying Column Generation to Machine Scheduling." The final chapter by François Vanderbeck, "Implementing Mixed Integer Column Generation," reviews how to set-up the Dantzig-Wolfe reformulation, adapt standard MIP techniques to the column generation context (branching, preprocessing, primal heuristics), and deal with specific column generation issues (initialization, stabilization, column management strategies).

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.

Applications of Optimization with Xpress-MP