| Article ID: | iaor2002476 |
| Country: | Netherlands |
| Volume: | 99 |
| Issue: | 1 |
| Start Page Number: | 79 |
| End Page Number: | 93 |
| Publication Date: | Dec 2000 |
| Journal: | Annals of Operations Research |
| Authors: | Elloumi Sourour, Faye Alain, Soutif Eric |
| Keywords: | programming: integer |
This paper presents a general decomposition method to compute bounds for constrained 0–1 quadratic programming. The best decomposition is found by using a Lagrangian decomposition of the problem. Moreover, in its simplest version this method is proved to give at least the bound obtained by the LP-relaxation of a non-trivial linearization. To illustrate this point, some computational results are given for the 0–1 quadratic knapsack problem.