An algorithm for quadratic zero-one programs

The authors present an algorithm for the quadratic zero-one minimization by reformulation of the problem into an equivalent concave quadratic minimization. They then specialize an algorithm proposed by Kalantari and Rosen, which globally minimizes a concave quadratic function over arbitrary polytopes. The algorithm exploits the special structure of the problem. Given a set of conjugate directions to the Hessian, the authors construct a linear convex envelope over a ‘tight’ containing parallelopiped, by solving 2n linear programs each solvable in O(n) time, n being the dimension of the problem. A bound on the maximum difference in the value of the quadratic function and the convex envelope may be obtained, which provides a global measure of underestimation. A branch-and-bound method is presented in which subproblems are defined by fixing a variable at zero or one. For each subproblem, the authors obtain a lower bound by minimizing the linear convex envelope over the feasible region of the subproblem. Computational experience with the algorithm is also presented.