Efficient methods for solving quadratic 0–1 knapsack problems

We propose an heuristic algorithm and an exact branch and bound algorithm for the problem of maximizing a quadratic function in 0–1 variables which are subject to a linear inequality. The proposed algorithms aim at determining, at every step of the procedure, variables which can be fixed to values that are both feasible and optimal for certain subproblems. The algorithms make repeated use of the L2-best linear approximation of the objective function and use for variable fixation conclusions derived from Lagrangean relaxation, order relations and constraint pairing. We investigate the role of each of the three variable fixation techniques using computational tests. Extensive computational results are presented comparing the proposed heuristic and exact algorithm with previously known ones. The conclusions show that the solution produced by the proposed heuristic algorithm is, on the average, within 1% of the optimum and that the number of nodes examined in the proposed exact algorithm is dramatically smaller than the ones examined in published methods.