Predicting the Processing Effort for Block Relocation Problems

In this paper, we propose a machine learning-based prediction approach for the block relocation problem. The target concept to be captured is the minimum number of relocations needed to clear all stacks of a given configuration. Since the problem is NP-hard, an exact determination of this value is computationally expensive. Therefore, quick and precise estimates are highly valuable, especially when the problem appears in hierarchical optimization contexts as a subproblem of another optimization problem, for example. We propose a design and training concept for a convolutional neural network that is capable of achieving accurate predictions on benchmark instances from the literature. The computational results further show that it is able to outperform competitor approaches like lower bounds, alternative machine learning techniques, and fast heuristics in terms of speed and common error metrics on most instance classes.