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


FB3 Cutting and Packing
June 11, 2021  10:45 AM
3 - TC Koopmans

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.