Article ID: | iaor20133911 |
Volume: | 207 |
Issue: | 1 |
Start Page Number: | 137 |
End Page Number: | 160 |
Publication Date: | Aug 2013 |
Journal: | Annals of Operations Research |
Authors: | Landete Mercedes, Monge Juan, Rodrguez-Cha Antonio |
Keywords: | packing, inequality problems |
An alternative formulation for the set packing problem in a higher dimension is presented. The addition of a new family of binary variables allows us to find new valid inequalities, some of which are shown to be facets of the polytope in the higher dimension. We also consider the Winner Determination Problem, which is equivalent to the set packing problem and whose special structure allows us to easily implement these valid inequalities in a very easy way. The computational experiments illustrate the performance of the valid inequalities and obtain good results.