Construction of the facets of the polytope of the quadratic knapsack problem

Construction of the facets of the polytope of the quadratic knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor20052832
Country: France
Volume: 37
Issue: 4
Start Page Number: 249
End Page Number: 271
Publication Date: Oct 2003
Journal: RAIRO Operations Research
Authors: ,
Keywords: knapsack problem
Abstract:

We build facets of the quadratic 0–1 knapsack polytope following two different approaches. The quadratic 0–1 knapsack polytope is included in the Boolean quadric polytope introduced by Padberg for unconstrained 0–1 quadratic problem. So in a first approach, we ask the question which are the facets of the Boolean quadric polytope that are still facets of the quadratic 0–1 knapsack polytope. Results for this problem are given for the cut inequality introduced by Padberg. We give necessary and sufficient conditions for which the cut inequality induces a facet of the quadratic 0–1 knapsack polytope and when these conditions are not satisfied we give a lifting of the inequality. In a different way, following the linearization technique of Adams and Sherali, we build facets of the quadratic 0–1 knapsack polytope from facets of the linear 0–1 knapsack polytope multiplying a linear inequality by a variable xi or &xmacr;i=1−xi. We show that this approach gives facets of the quadratic 0–1 knapsack polytope and we extend it to multiplying an inequality that induces a facet of the quadratic 0–1 knapsack polytope. To conclude, we give numerical results of a cutting plane algorithm involving cuts built following these two schemes.

Reviews

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