Group for Research in Decision Analysis

G-2000-59

A Simple Enumerative Algorithm for Unconstrained 0-1 Quadratic Programming

, , and

We modify the algorithm of Pardalos and Rodgers [40] for the minimization of a pseudo-boolean quadratic function by introducing an easy to compute lower bound as well as a variable fixation test, based on the concept of roof-duality. Numerical results show that the new algorithm outperforms the original algorithm of Pardalos and Rodgers.

, 24 pages