Advances in shortest path based column generation for integer programming

Column generation is a pricing scheme for solving large scale linear programming (LP) problems. This process involves introducing variables corresponding to violated dual constraints dynamically during the solution process of the LP. When embedded in a branch-and-cut algorithm, the resulting branch-price-and-cut algorithm can be used to solve many difficult and large scale integer programming (IP) problems.;Branch-price-and-cut algorithms are among the most successful exact optimization approaches for solving many routing and scheduling problems. This is due, in part, to the availability of extremely efficient and effective dynamic programming algorithms for solving the pricing problem, as well as the availability of efficient and effective branching schemes and cutting planes that drive integrality. In terms of branch-price-and-cut, two obstacles we face today are (1) being able to solve harder and larger pricing problems, and (2) solving mixed-integer column generation formulations that suffer from relatively weak LP bounds compared to the more traditional 0-1 set partitioning type. As part of the work presented in this thesis, we encounter column generation formulations motivated by real life problems that require overcoming both types of challenges.;The first part of this thesis is dedicated to solving the resource constrained shortest path problem (RCSPP) arising in column generation pricing problems for formulations involving extremely large networks and a huge number of local resource constraints. We present a relaxation-based dynamic programming algorithm that alternates between a forward and a backward search. Each search employs bounds derived in the previous search to prune the search, and between consecutive searches, the relaxation is tightened using a set of critical resources and a set of critical arcs over which these resources are consumed. The algorithm is tested on practical instances of the dial-a-flight problem and is shown to significantly outperform standard dynamic programming techniques.;The second part of this thesis also focuses on the pricing problem. In many situations, incorporating relevant practical constraints results in pricing problems that do not give rise to pure RCSPPs, but more complex variants, such as the fixed charge shortest path problem (FCSPP) in which the amount of resource consumed is itself a continuous bounded variable. By exploiting the structure of optimal solutions to FCSPP, we design and implement a solution approach that relies on solving multiple RCSPPs, and therefore can again make use of extremely efficient and effective dynamic programming algorithms. Computational results on three different classes of problems are reported including the split delivery vehicle routing problem, parallel machine scheduling problems with controllable processing times, and multi-period inventory routing problems.;In the third and final part of this thesis, we present a new branch-price-and-cut algorithm for the inventory routing problem (IRP), a difficult mixed 0-1 problem that requires considerable effort in preprocessing, branching, and cut generation outside the realms of branch-price-and-cut for traditional 0-1 problems. Apart from considering a more general problem than previously considered in the literature, we extend the algorithm developed for FCSPP to solve the pricing problem efficiently. In addition to preprocessing, we use the boundary constraints to restrict the set of columns that are generated. Furthermore, we extend a class of cuts known for the vehicle routing problem, and develop a new class of cuts specifically for IRP to tighten the formulation even further. Both the branching schemes and cuts preserve the structure of the pricing problem making them efficiently implementable within a branch-price-and-cut algorithm. Computational results are reported for several practical instances related to managing the supply chain of a large petrochemical company. The results compare favorably against an alternative branch-and-cut algorithm.