Penalty computations for the set partitioning problem

The computation of penalities associated with the continuous relaxation of integer programming problems can be useful to derive conditional and relational tests which allow to fix some variables at their optimal value or to generate new constraints (cuts). The authors study in this paper the computation and the use of penalties as a tool to improve the efficiency of algorithms for solving set partitioning problems. This leads to a preprocessing scheme which can be embedded within any exact or approximate algorithm. The strength of these penalties is illustrated through computational results on some real-world set partitioning problems.