On a cutting plane heuristic for the stable roommates problem and its applications

Abstract

We propose a new cutting plane heuristic for the classical stable roommates problem. Our approach utilises a new linear programming formulation for the problem, and the underlying geometric properties of the fractional solution to construct the violated inequality. We test the approach on moderate size problems, with encouraging computational performance. To further illustrate the versatility of this approach, we also show how it can be suitably extended to handle variants of the basic stable roommates model.