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: | Rao M.R., Gottlieb Elsie Sterbin |
Keywords: | programming: assignment |
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.