The generalized assignment problem: Valid constraints and facets

The generalized assignment problem: Valid constraints and facets

0.00 Avg rating0 Votes
Article ID: iaor1991658
Country: Netherlands
Volume: 46
Issue: 1
Start Page Number: 31
End Page Number: 52
Publication Date: Jan 1990
Journal: Mathematical Programming (Series A)
Authors: ,
Keywords: programming: assignment
Abstract:

Three classes of valid inequalities based upon multiple knapsack constraints are derived for the generalized assignment problem. General properties of the facet defining inequalities are discussed and, for a special case, the convex hull is completely characterized. In addition, the authors prove that a basic fractional solution to the linear programming relaxation can be eliminated by a facet defining inequality associated with an individual knapsack constraint.

Reviews

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