TY - JOUR
T1 - Facets of the complementarity knapsack polytope
AU - De Farias, I. R.
AU - Johnson, E. L.
AU - Nemhauser, G. L.
PY - 2002/2
Y1 - 2002/2
N2 - 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 MIP. 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 fight 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.
AB - 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 MIP. 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 fight 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.
KW - Complementarity
KW - Facet
KW - Knapsack problem
UR - http://www.scopus.com/inward/record.url?scp=0036474570&partnerID=8YFLogxK
U2 - 10.1287/moor.27.1.210.335
DO - 10.1287/moor.27.1.210.335
M3 - Article
AN - SCOPUS:0036474570
SN - 0364-765X
VL - 27
SP - 210
EP - 226
JO - Mathematics of Operations Research
JF - Mathematics of Operations Research
IS - 1
ER -