A polyhedral approach for a constrained quadratic 01 problem
In this paper we consider the problem of optimizing a quadratic pseudo-Boolean function subject to the cardinality constraint ? 1 ? i ? n x i = k with a polyhedral method. More precisely we propose a study of the convex hull of feasible points included in the Padberg's Boolean quadric polytope and satisfying the cardinality constraint. Specifically, we investigate the connection with the Boolean quadric polytope and study a facet family. The relationship with two other polytopes of the literature is also explored.
constrained quadratic 01 problem polytope facets faces