On the 0/1 knapsack polytope

On the 0/1 knapsack polytope

0.00 Avg rating0 Votes
Article ID: iaor19981414
Country: Netherlands
Volume: 77
Issue: 1
Start Page Number: 49
End Page Number: 68
Publication Date: Apr 1997
Journal: Mathematical Programming
Authors:
Keywords: knapsack problem
Abstract:

This paper deals with the 0/1 knapsack polytope. In particular, we introduce the class of weight inequalities. This class of inequalities is needed to describe the knapsack polyhedron when the weights of the items lie in certain intervals. A generalization of weight inequalities yields the so-called ‘weight-reduction principle’ and the class of extended weight inequalities. The latter class of inequalities includes minimal cover and (1, k)-configuration inequalities. The properties of lifted minimal cover inequalities are extended to this general class of inequalities.

Reviews

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