Guiding Column Generation using Deep Reinforcement Learning Trainee and Training Device Optimization
Publicerad
Författare
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Scheduling Problem, Integer Linear Programming, Column Generation, Graph Neural Networks, Deep Reinforcement Learning.