Master's Thesis presentation, Karin Hult

Abstract: Aircraft routing is a complicated optimization problem which can be modelled as a form of resource-constrained integer multi-commodity network flow problem. When optimizing this problem, a good lower bound is useful to assess the quality of feasible solutions. The current technique to calculate lower bounds is very fast, but does several relaxations on top of each other. This fact makes it probable to find a method to strengthen the lower bound. This master thesis examines an alternative method of calculating a lower bound by performing Lagrange relaxation with respect to only one constraint group, which theoretically would lead to a stronger lower bound. Subgradient optimization with Polyak step-size are used to solve the Lagrange dual problem. Tests are performed both with realistic implementations, and with idealistic parameters to investigate the potential of Lagrange relaxation, and solving the Lagrange dual problem with subgradient optimization. Lastly the results are compared to an LP-based relaxation of the original problem. The Lagrange relaxation shows promise as the idealized tests resulted in a significant improvement of lower bound for most of the studied test cases. However, the realistic implementations of subgradient optimization did not perform consistently well for all test cases; this indicates that improvements to the implementations are required for this method of solving the Lagrange dual problem to be usable in practice.

Supervisor: Andreas Westerlund