Partitioning a permutation graph: algorithms and an application

In this paper we discuss the problem of partitioning a permutation graph into cliques of bounded size, and describe a real-life application of this problem encountered at a manufacturing company. 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-life instances. Test results are given, both for real-life instances and randomly generated instances. As far as we are aware, this is the first implementation of an algorithm based on bounded clique-width.status: publishe