K. Piechowiak, M. Drozdowski, E. Sanlaville
Selection of fast algorithm portfolios for 2D packing problem is considered. The 2D packing problem analyzed here consists in placing rectangles on a strip of a given width for minimum strip length. While solving combinatorial optimization problems longer runtimes increase chances of obtaining higher quality solutions. This means that solution quality vs runtime trade-off exists. Given some limited runtime a method is needed to provide the best solution possible. Usually a single algorithm outperforming all other methods under all possible conditions does not exist. Therefore, algorithm portfolios can reliably provide high quality solutions in the limited runtime. We propose a method choosing algorithm portfolios on the basis of the algorithm performance on a set of training instances. The portfolios cover the instances with the best solutions which could be obtained in the given runtime, subject to the minimum overall computational cost of the selected algorithms. We demonstrate that our method is capable of porting solution quality from the training datasets to the validation datasets.
Keywords: Heuristics, runtime-quality trade-off, 2D packing, algorithm selection problem, algorithm portfolios
Scheduled
FB3 Cutting and Packing
June 11, 2021 10:45 AM
3 - TC Koopmans
