Pushing the limits for large-scale discrete optimisation: New mathematics and algorithms for methods used together with Dantzig-Wolfe decomposition.
Over the last decades, there has been an impressive development of methods for solving discrete optimisation problems. In particular, the Mixed-Integer Programming (MIP) solvers—such as Gurobi and SCIP—have become exceptionally powerful tools that can solve a variety of challenging and practically relevant problems. However, it is still common that these state-of-the-art solvers fail to deliver a solution to challenging instances even within weeks or years of computational time, due to the problems being NP-hard. For these types of problems, the use of decomposition methods that exploit problem structure can be the remedy. Instead of solving one large problem, one solves a series of simpler problems in a way that gives a convergence to solving the original problem. This project specifically addresses Dantzig-Wolfe decomposition, which is a standard approach for computationally challenging problems in important application domains such as vehicle routing and aviation planning, where MIP solvers are known to perform poorly.
MIP solvers cannot be directly used in combination with Dantzig-Wolfe decomposition, and instead Branch-and-Price(-and cut) solvers are applied. Even if showing great potential, generic such solvers are not as mature as the MIP solvers and research is needed to both improve computational performance and to make them more adaptive to different types of problem structures. The purpose of this project is to develop new mathematical theory and algorithm components to improve the computational performance of optimisation methods used in combination with Dantzig-Wolfe decomposition.
Project information
This project is funded as a WASP Academic Doctoral Student position for PhD student Diana Gutierrez Diaz. Main supervisor is Elina Rönnberg and co-supervisor is Marco Lübbecke (RWTH Aachen University).
