A lower bound for a constrained quadratic 0–1 minimization problem Original Research Article

Given a quadratic pseudo-Boolean functionf(x1, …, xn) written as a multilinear polynomial in its variables, Hammer et al. [7]have studied, in their paper “Roof duality, complementation and persistency in quadratic 0–1 optimization”, the greatest constant c such that there exists a quadratic posiform φ satisfyingf = c + φ for all xϵ {0, 1}n. Obviously c is a lower bound to the minimum of f. In this paper we consider the problem of minimizing a quadratic pseudo- Boolean function subject to the cardinality constraint ∑i = 1, n xi = k and we propose a linear programming method to compute the greatest constant c such that there exists a quadratic posiform φ satisfying f = c + φ for all x ϵ {0, 1}n with ∑i = 1, n xi = k. As in the unconstrained case c is a lower bound to the optimum. Some computational tests showing how sharp this bound is in practice are reported.