Bivalent quadratic programming problem - A computational study (Q801811)

Consider the problem of minimizing a quadratic function of n zero-one variables, i.e. minimize \(x^ tQx\), subject to \(x\in B^ n_ 2\), where Q is an \(n\times n\) symmetric matrix and \(B_ 2=\{0,1\}\). A branch-and- bound algorithm is proposed. Problems which are difficult to solve by this method are identified and a heuristic algorithm for their solution is suggested. Computational experience relating to the effectiveness of the two algorithms is indicated.