Group for Research in Decision Analysis


Valid inequalities and separation algorithms for the set partitioning problem

, , and

In this article we investigate some strategies for solving set partitioning problems (SPP), in particular the gains in computational efficiency that can be obtained by introducing cutting planes based on some rank-1 Chvátal-Gomory inequalities and clique inequalities. We show that for many instances of the SPP, the introduction of some of these cutting planes into the standard SPP model enables a commercial solver such as CPLEX to compute optimal solutions more efficiently.

, 17 pages

This cahier was revised in July 2015