PUB - Publikationen an der Universität Bielefeld

Solving real-world combinatorial optimization problems with traditional operations research methods can be a costly and time-consuming endeavor, often requiring the development of completely new methods or significant modification of exist- ing techniques. This has led many organizations to forego the use of analytical decision-making tools, as the costs associated with these methods can outweigh the potential savings. In this thesis, we investigate the use of machine learning techniques, especially deep reinforcement learning methods, to automate the design of problem-specific solution approaches for combinatorial optimization problems. Instead of focusing on approaches that learn to generate solutions end-to-end, we ex- amine the use of machine learning to learn heuristics for extensive search procedures. Specifically, we investigate the use of deep neural networks to learn problem-specific, heuristic components that can be incorporated into high-level, problem-agnostic search methods. By automating the design of the problem-specific components, the overall solution approach can be easily tailored to the characteristics of the problem instances at hand and make the use of optimization technologies more accessible to a wider range of organizations.
In this thesis, we develop four novel approaches that leverage deep learning techniques to solve combinatorial optimization problems. The first approach is a tree search approach for the container pre-marshalling problem, in which deep neural networks are used to make branching and bounding decisions. The second approach is a large neighborhood search metaheuristic for routing problems that learns the repair operator using deep reinforcement learning. The third approach uses a conditional variational autoencoder to learn a mapping from discrete routing problem solutions to a continuous space that can be searched using any continuous optimization method. The fourth approach presents a simple technique for extending existing learning-based construction heuristics by an extensive and efficient search mechanism. We evaluate the performance of the proposed approaches on a variety of combinatorial optimization problems. The results suggest that machine learning techniques can be used to automate the design of problem-specific components of heuristic search methods, potentially lowering the barriers to entry for the use of optimization technologies in a wide range of novel use cases.