zbMATH — the first resource for mathematics

Facets of the complementarity knapsack polytope. (English) Zbl 1082.90586
Summary: 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 tight bounds for the lifting coefficients, and we present two families of facet-de.ning 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.

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C35 Programming involving graphs or networks
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C27 Combinatorial optimization
Full Text: DOI