Automatically learning to solve optimization problems with deep reinforcement learning: The quest for feasibility

• Applicant: Professor Dr. Kevin Tierney
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing ; Management and Marketing
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 521243122

Optimization problems play a critical role in a wide variety of industries and research fields. Solving optimization problems quickly and as close to optimality as possible is essential for providing effective decision support to decision makers. However, designing algorithms and solvers for solving optimization problems is a time-consuming process involving significant human expertise both in terms of the problem domain and knowledge of optimization methods. Furthermore, solvers rarely use data-driven techniques, i.e., using a set of representative problem instances to design an algorithm that is most effective for those instances. Recently, a number of approaches have been designed to automatically develop optimization methods for specific problems using deep reinforcement learning. These approaches fine-tune a solution algorithm specifically for a given problem and class of problem instances. Despite the success of these approaches on simple problems such as the traveling salesperson problem and capacitated vehicle routing problem, they have not yet been applied to more challenging problems in operations research that consist of numerous side constraints and interacting problem components. In particular, these problems are challenging to solve because it is hard to find feasible solutions. That is, simply the task of finding a solution satisfying all of the constraints poses a significant hurdle to modern solvers. This project proposes novel search and learning mechanisms for achieving feasibility, drawing on years of experience in applying machine learning mechanisms to optimization problems. In terms of search, the project will investigate problem-independent mechanisms including heuristic backtracking, Monte-Carlo roll outs and efficient active search. Regarding learning, the project proposes novel loss functions, curriculum learning and mechanisms for targeting the feasibility boundary present in optimization problems. Finally, the project will investigate a class of extremely difficult problems involving interdependent components, such as pickups and deliveries, and solve these with novel embedding techniques and decomposition. The outcome of the project will be highly-effective, problem independent reinforcement learning methods that are thoroughly tested on a wide range of optimization problems where finding feasible solutions is challenging.

• DFG Programme: Research Grants