Exact Algorithms for a Loading Problem with Bounded Clique Width

In this paper we discuss a special pallet-loading problem, which we encountered at a manufacturing company. In graph-theoretical terms, the problem is equivalent to partitioning a permutation graph into bounded-size cliques. We formulate the problem as an integer program, and present two exact algorithms for solving it. The first algorithm is a branch-and-price algorithm based on the integer-programming formulation; the second one is an algorithm based on the concept of bounded clique width. The latter algorithm was motivated by the structure present in the real-world instances. Test results are given, both for real-world instances and randomly generated instances. As far as we are aware, this is the first implementation of an algorithm based on bounded clique width.