On tightening cover induced inequalities

On tightening cover induced inequalities

0.00 Avg rating0 Votes
Article ID: iaor1996618
Country: Netherlands
Volume: 60
Issue: 3
Start Page Number: 335
End Page Number: 343
Publication Date: Aug 1992
Journal: European Journal of Operational Research
Authors: ,
Keywords: cliques
Abstract:

Here the authors describe computationally efficient procedures for tightening cover induced inequalities by using 0-1 knapsack constraints and, if available, cliques whose variables are included in the cover. An interesting application is the case where the cover is implied by the knapsack constraint. The tightening is achieved by increasing the coefficients of the cover inequality. The new constraint is 0-1 equivalent to and LP tighter than the original one. The computational complexity of the procedures is O(nlogn), where n is the number of variables in the cover.

Reviews

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