Master thesis presentation Anton Lindén, MPCAS

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.
Large ILP models are often solved using an algorithm known as Column Genera-
tion (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 Jeppesen, a Boeing company, and investi-
gated the possibility of using Deep Reinforcement Learning (DRL) to generate new
variables in CG for a scheduling problem for airline pilots. Results show that it is
possible to teach an agent a policy that slightly improves the quality of the gener-
ated 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.

Supervisor: Adam Wojciechowski
Examiner: Mats Granath
Opponent: Nils Hedberg