Monte Carlo Tree Search and Instance Space Analysis for the 0-1 Knapsack Problem

In recent years, the scientific community has shown a growing interest in machine learning algorithms applied in the context of combinatorial optimization. Typically, the performance of a combinatorial optimization algorithm heavily relies on how well the algorithm is able to exploit the combinatorial properties of the specific problem at hand. This manifests itself, for example, in the necessity to model a problem in an appropriate way so that the corresponding search space can be explored efficiently. Similarly, one can expect that machine learning algorithms applied in the context of
combinatorial optimization also need to exploit combinatorial properties to perform well. However, this is often not straightforward since these machine learning algorithms have rarely been designed for the purpose of combinatorial
optimization. In this thesis, we investigate to what extent current state-of-the-art practices for the 0-1 knapsack problem can be improved by integrating combinatorial knowledge into the Monte Carlo tree search algorithm and the instance space analysis methodology.

We investigate this question through two case studies. The first case study focuses on the Monte Carlo tree search algorithm, which is a popular reinforcement learning algorithm mainly used in game playing to learn promising moves. We demonstrate that the algorithm can be slightly adapted to solve combinatorial optimization problems by exploring a search space tree. We investigate how different forms of combinatorial information can be integrated into the algorithm to efficiently explore the search space. The resulting algorithm is instantiated for two problems from the literature - the 0-1 knapsack problem and the quay crane scheduling problem with non-crossing constraints - and its performance is compared to the state-of-the-art algorithms for both problems.

The second case study is centered around the instance space analysis methodology, which can be used to analyze various properties of problem instances based on a representation of these instances as feature vectors. A generator for 0-1 knapsack problem instances is proposed. This generator enforces a number of combinatorial properties related to the inclusionwise maximal solutions of these instances. We compare the hardness of the resulting instances with the hardest instances from the literature and investigate their location in the instance space. New 0-1 knapsack features based on inclusionwise maximal solutions are defined and new structural results are proven that allow us to formulate polynomial and pseudopolynomial time algorithms for calculating them. We compare these features with existing features from the literature, conduct an instance space analysis and investigate the extent to which these features are related to the hardness of a problem instance.