An anytime tree search algorithm for two-dimensional two- and three-staged guillotine packing problems
[libralesso_anytime_2020] proposed an anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem (https://www.roadef.org/challenge/2018/en/index.php). The resulting program was ranked first among 64 participants. In this article, we generalize it and show that it is not only effective for the specific problem it was originally designed for, but is also very competitive and even returns state-of-the-art solutions on a large variety of Cutting and Packing problems from the literature. We adapted the algorithm for two-dimensional Bin Packing, Multiple Knapsack, and Strip Packing Problems, with two- or three-staged exact or non-exact guillotine cuts, the orientation of the first cut being imposed or not, and with or without item rotation. The combination of efficiency, ability to provide good solutions fast, simplicity and versatility makes it particularly suited for industrial applications, which require quickly developing algorithms implementing several business-specific constraints. The algorithm is implemented in a new software package called PackingSolver.
Code (1)
Tasks
Vocal Bursts Valence PredictionSimilar Papers 제목 키워드 기반
A Generic Complete Anytime Beam Search for Optimal Decision Tree
Finding an optimal decision tree that minimizes classification error is known to be NP-hard. While exact algorithms based on MILP, CP, SAT, or dynamic programming guarantee optimality, they often suffer from poor anytime…
Anytime Optimal Decision Tree Learning with Continuous Features
In recent years, significant progress has been made on algorithms for learning optimal decision trees, primarily in the context of binary features. Extending these methods to continuous features remains substantially mor…
An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem
In this article, we present the anytime tree search algorithm we designed for the 2018 ROADEF/EURO challenge glass cutting problem proposed by the French company Saint-Gobain. The resulting program was ranked first among…
Anytime Probabilistically Constrained Provably Convergent Online Belief Space Planning
Taking into account future risk is essential for an autonomously operating robot to find online not only the best but also a safe action to execute. In this paper, we build upon the recently introduced formulation of pro…
Extremely Fast Decision Tree
We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of …
General Classification