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).
