Combining Machine Learning and Branch-Price-and-Cut to solve Vehicle Routing Problems

• Applicant: Professor Dr. Christian Tilk
• Subject Area: Management and Marketing
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 503190360

The MaLeBPCTop project aims to generate new insights into the use of machine learning in operations research methods to solve combinatorial optimization problems. The key question is how machine learning can be used in operations research algorithms because combinatorial optimization problems are very different from most problems that are currently tackled by machine learning.The focus of the project is on the exact solution of vehicle routing problems using branch-price-and-cut (BPC). BPC is one of the leading methods for the exact solution of vehicle routing problems. It is a branch-and-bound procedure in which every branch-and-bound node is solved by column generation. In BPC algorithms, some algorithmic decisions are made according to the “greedy principle” or according to “best practice”. The central hypothesis of the MaLeBPCTop project is that, by using known machine learning algorithms, algorithmic components can be configured by learning from previously solved problem instances in order to make better decisions. The goal is to design more effective BPC algorithms, by learning selected algorithmic decisions while maintaining the accuracy of the BPC algorithm.The evaluation of a decision made in the BPC is difficult, even afterwards, if the instance has already been optimally solved with BPC. Of course, the BPC algorithm can be executed several times and different configurations can be used for an algorithmic decision to determine the best decision (in retrospect). For most of the algorithmic decisions to be learned, however, high dimensionality and recurring occurrences mean that the very high number of necessary BPC runs would be far too computationally complex. Therefore, various strategies for determining a decision to be learned are examined. Both algorithmic decisions of the master problem and decisions to solve the pricing problem are investigated. In addition to classic learning methods such as random forests, deep learning methods based on graph neural networks are also used. To assess the use of machine learning, there is primarily only one criterion in exact algorithms such as BPC: the solution time. The time-consuming training and testing phase of the learning algorithms therefore always takes place outside of the BPC algorithm.

• DFG Programme: Research Grants