Facets of the complementarity knapsack polytope

I. R. De Farias, E. L. Johnson, G. L. Nemhauser

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

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 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.

Original languageEnglish
Pages (from-to)210-226
Number of pages17
JournalMathematics of Operations Research
Volume27
Issue number1
DOIs
StatePublished - Feb 2002

Keywords

  • Complementarity
  • Facet
  • Knapsack problem

Fingerprint Dive into the research topics of 'Facets of the complementarity knapsack polytope'. Together they form a unique fingerprint.

Cite this