2667. Accelerated convergence in column generation by a modified master problem
Invited abstract in session WC-12: Workforce assignment, stream Scheduling and Project Management.
Wednesday, 12:30-14:00Room: Clarendon SR 1.02
Authors (first author is the speaker)
| 1. | Sebastian Van Thienen
|
| Mathematics, UAntwerpen |
Abstract
We discuss the column generation algorithm in the context of crew scheduling in aviation. This algorithm naturally arises when combining the Dantzig-Wolfe decomposition with the classical simplex algorithm for solving linear programs, and it leverages very fast shortest path algorithms that can be applied to the personalized time-space graph representations of every crew member in parallel.
However, this algorithm suffers from degenerate steps, essentially slowing down convergence, leading to the tailing-off effect. In this talk we discuss how we can overcome these convergence challenges by regularizing the master problem, which makes it quadratic instead of linear. We analyze the mathematical structure of this regularized formulation and present specialized algorithms for its efficient solution.
Our main contribution lies in explaining how to solve these modified master problems efficiently, and in demonstrating how the new formulation mitigates degeneracy and accelerates convergence of the column generation algorithm.
Keywords
- Large Scale Optimization
- Scheduling
- Programming, Quadratic
Status: accepted
Back to the list of papers