Towards a framework for predicting packing algorithm performance across instance space

Abstract

Finding the conditions under which packing algorithms succeed or fail with respect to a set of test instances is crucial for understanding their strengths and weaknesses, and for automated packing algorithm selection. This paper tackles the important task of objective packing algorithm selection. A framework for understanding the relationship between critical features of packing problem instances and the performance of packing algorithms is proposed. The framework can be used to predict algorithm performance on previously unseen instances with high accuracy and can be applied to find predictions in other instances of cutting and packing problems. It can also be applied to determine the relative strengths and weaknesses of each algorithm within the instance space. The effectiveness of the framework is demonstrated using the two-dimensional strip packing problem as a case study.