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.