✍ Scribed by Alain Billionnet; Alain Faye
No coin nor oath required. For personal study only.
Given a quadratic pseudo-Boolean function f (x 1, . , XJ 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-I optimization", the greatest constant c such that there exists a quadratic posiform 4 satisfyingf= c + 4 for all x E {0, 1)". 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 CiZl n xi = k and we propose a linear programming method to compute the greatest constant c such that there exists a quadratic posiform 4 satisfyingf= c + 4 for all x E {O,l}" with C,=l,n xi = k. As in the unconstrained cast c is a lower bound to the optimum. Some computational tests showing how sharp this bound is in practice are reported.
📜 SIMILAR VOLUMES