Abstract

The ability of the humans to manually solve NP-hard problems had not received much attention of the scientific community. This paper considers the Strip Packing Problem (SPP), in which a set of rectangular pieces has to be placed orthogonally in a container with a given width and an infinite length. The pieces are not allowed to overlap (i.e. be stacked one over the other). The aim of the SPP is to minimize the overall length of the strip. In this paper, we have developed a computational game to allow manual solutions by expert gamers for different instances of the problem. The main contribution of the paper is the presentation of an algorithm based on patterns and data mining retrieved from the results achieved by expert gamers. The proposed algorithm is based on decision-trees and heuristics proposed in literature. Finally, the proposed approach is able to find the best-known solutions for the 94.3% of a set of instances proposed in the literature, and 79% for instances generated randomly.