Alternative formulations for the Set Packing Problem and their application to the Winner Determination Problem

Alternative formulations for the Set Packing Problem and their application to the Winner Determination Problem

0.00 Avg rating0 Votes
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: , ,
Keywords: packing, inequality problems
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.