Guiding Column Generation using Deep Reinforcement Learning Trainee and Training Device Optimization

Abstract

Many optimization problems can be formulated as a Integer Linear Program (ILP), which is an optimization problem that involves minimizing or maximizing a linear objective function subject to linear constraints and integrality requirements. Some examples include train scheduling, airline crew scheduling and production planning. ILP models with an exponentially growing set of variables are often solved using an algorithm known as Column Generation (CG). CG iteratively improves the objective function value by generating new variables, or columns, without considering every possible variable in the ILP model. This thesis was performed together with Jeppe sen, a Boeing company, and investigated the possibility of using Deep Reinforcement Learning (DRL) to generate new variables in CG for a scheduling problem for air line pilots. Results show that it is possible to teach an agent a policy that slightly improves the quality of the generated variables in this specific problem. However, it is still unclear whether or not the benefits of using DRL outweighs the extra effort of setting up and training an agent.