This research presents a very efficient method of solving a broad class of large-scale capacitated resource management problems by introducing a new formulation and decomposition. A heuristic called Likelihood of Assignment is utilized not only to find high quality initial integer feasible solutions, but also to guide the Branch-and-Price (B&P) Algorithm towards stabilization. Although Column Generation (ColGen) is thought to be the ideal approach to attack large-scale linear problems, it has been found that the textbook variety of ColGen algorithms are rather problematic during the Heading-in Phase. To alleviate the Heading-In Effect, and to start with good and valid lowerbounds, strategies for constructing the initial dual vector are provided, which is guaranteed to be feasible for the first Restricted Master Problem (RMP). Dual vectors obtained from RMP’s at any iteration are further manipulated in order to prevent parallel and astray columns, which cause degeneracy and stalling. A subproblem selection scheme is also proposed to accelerate the convergence. The proposed techniques are thoroughly covered in the first two chapters of this thesis for theWorkforce Planning with Cross-Training Problem and they provide superior results to CPLEX by being 10 times faster on average and having 20% better solution gap quality in the same amount of time. In the third chapter of the dissertation, an Agent-Based Tabu Algorithm for the Workforce Scheduling Problem with Stochastic Demand is introduced to yield quality starting solutions. These starting solutions then feed a stabilized Nested ColGen Algorithm. The Nested ColGen algorithm not only provides a valid lower bound, but also, improve the integer feasible solution towards optimality with high quality incoming columns. Likelihood of Assignment’s effectiveness in this particular problem structure for accelerating and stabilizing the ColGen Algorithm is also showcased. In the final chapter, we show that, the applicability of Likelihood of Assignment and the aforementioned acceleration and stabilization schemes are indeed viable for very well-known capacitated resource management problems such as Train (Vehicle) Routing, Capacitated Facility Location, and Airline Crew Pairing and Rostering Problems. Therefore, the approach presented in this research is not designed solely for Workforce Planning and Scheduling Problems, but it can be slightly modified to solve any type of Capacitated Resource Management Problem with block angular structure. Recommendations for parameter setup and performance tuning are also given for different problem characteristics and data input.
Citation
Uygur, A. (2011) Acceleration and Stabilization Techniques for Column Generation Applied to Capacitated Resource Management Problems. Ph.D. Thesis, Lehigh University, Bethlehem, PA, USA.