Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem

摘要

In this paper we consider the constant rank unconstrained quadratic 0-1 optimization problem, CR-QP01 for short. This problem consists in minimizing the quadratic function (x, Ax) + (c, x) over the set {0,1}(n) where c is a vector in R-n and A is a symmetric real n x n matrix of constant rank r.