Facets of the complementarity knapsack polytope

Facets of the complementarity knapsack polytope

0.00 Avg rating0 Votes
Article ID: iaor2004390
Country: United States
Volume: 27
Issue: 1
Start Page Number: 210
End Page Number: 226
Publication Date: Feb 2002
Journal: Mathematics of Operations Research
Authors: , ,
Keywords: knapsack problem
Abstract:

We present a polyhedral study of the complementarity knapsack problem. Traditionally, complementarity constraints are modeled by introducing auxiliary binary variables and additional constraints, and the model is tightened by introducing strong inequalities valid for the resulting mixed integer programming. We use an alternative approach, in which we keep in the model only the continuous variables, and we tighten the model by introducing inequalities that define facets of the convex hull of the set of feasible solutions in the space of the continuous variables. To obtain the facet-defining inequalities, we extend the concepts of cover and cover inequality, commonly used in 0–1 programming, for this problem, and we show how to sequentially lift cover inequalities. We obtain tight bounds for the lifting coefficients, and we present two families of facet-defining inequalities that can be derived by lifting cover inequalities. We show that unlike 0–1 knapsack polytopes, in which different facet-defining inequalities can be derived by fixing variables at 0 or 1, and then sequentially lifting cover inequalities valid for the projected polytope, any sequentially lifted cover inequality for the complementarity knapsack polytope can be obtained by fixing variables at 0.

Reviews

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