Algorithm selection and runtime prediction for the two dimensional bin packing problem : analysis and characterization of instances

Abstract

The bin packing problem (BPP) is one of the best-known combinatorial optimization problems. This problem is proven to be NP-hard despite its simple task setting. Since its first introduction in the 1960s, different exact and heuristic algorithms have been proposed for this problem. A variety of algorithms that obtain nearly optimal solutions have been presented in the last decade. However, the proposed methods have advantages and disadvantages, which depend on the specific instance to which they are applied. Designing an algorithm which finds the best possible solution for every possible instance is hard or, by analogy to the No-free-Lunch-Theorem, even impossible. Therefore, selecting the optimal solver for a specific problem can be used in industrial areas of the BPP to reduce the costs and resources needed for real-life problems. Many approaches have been proposed for the NP-hard problems to achieve better results on all available instances. One of them is the algorithm selection approach. The method predicts for each instance the algorithm which achieves the best performance. The procedure uses a set of intrinsic features computed from the problem instances, and a set of algorithms to predict the best algorithm for the particular instance. This thesis investigates the algorithm selection approach and the runtime prediction approach for the BPP. We considered two variations of the BPP, in the first case the items are oriented (O) and guillotine cuts are required (G), and in the second case the items can be rotated by 90 degrees (R) and guillotine cuts are also required (G). To use this method, we first introduce a set of features for the problem instances, which can be computed in polynomial time. Then we evaluate the performance of nine state of the art heuristics for the BPP. In order to evaluate these algorithms, we use 500 problem instances from two publicly available instance sets. We analyse the behavior of the algorithms on classes of problem instances with different attributes. Furthermore, we investigate which attributes define hard instances and whether an algorithm exist, which clearly outperforms the other algorithms. We analyse the behaviour of the algorithms on classes of problem instances with different attributes. Furthermore, we investigate which characteristics define hard instances and whether algorithms exist, which clearly preforms better than others. In the next step, we use the knowledge about the most appropriate algorithm and the newly developed features for each instance to train seven classification algorithms. The obtained models use supervised learning methods to predict the most appropriate algorithm for new and unseen instances. For each classifier, we test multiple parameter settings. We analyse the impact of preprocessing and data preparation techniques on the quality of the performance for the prediction models. Furthermore, we use a crossvalidation method as standard machine learning strategies to compare the prediction models. Our experiments show that the selection of an algorithm based on machine learning is able to beat all the single solver heuristics in terms of time - and solution quality. For the run time prediction approach we use additionally a newly generated dataset with a higher variety of instance sizes. The experimental results with different regression models show that the designed features can be used for the runtime prediction of the BPP-algorithms.