AN ALGORITHM FOR INDEFINITE INTEGER QUADRATIC-PROGRAMMING

We present an algorithm for finding the global minimum of an indefinite quadratic function over the integers contained in a compact, convex set. To find this minimum, the algorithm first transforms the problem into an equivalent problem with a separable objective function. It then uses a branch and bound search on the values of the constraints, rather than the variables, of the transformed problem.