The matching relaxation for a class of generalized set partitioning   problems
  This paper introduces a discrete relaxation for the class of combinatorial optimization problems which can be described by a set partitioning formulation under packing constraints. We present two combinatorial relaxations based on computing maximum weighted matchings in suitable graphs. Besides providing dual bounds, the relaxations are also used on a variable reduction technique and a matheuristic. We show how that general method can be tailored to sample applications, and also perform a successful computational evaluation with benchmark instances of a problem in maritime logistics. 
Phillippe Samer, Evellyn Cavalcante, Sebasti\'an Urrutia, Johan Oppen
cs.DS math.OC