LAGRANGEAN METHODS FOR THE 0-1 QUADRATIC KNAPSACK-PROBLEM

It is well known that the Lagrangean decomposition provides better bou nds than the Lagrangean relaxation does. Nevertheless, the Lagrangean decomposition bound is harder to compute than the Lagrangean relaxatio n bound. Thus, one might wonder what is the best Lagrangean method to use in a branch-and-bound algorithm. In this paper, we give an answer to such a question for the 0-1 Quadratic Knapsack Problem. We first st udy the Lagrangean decomposition for this problem and give new necessa ry optimality conditions for the dual problem which allow us to elabor ate a heuristic method for solving the Lagrangean decomposition dual p roblem. We then introduce this method in Chaillou-Hansen-Mahieu's bran ch-and-bound algorithm where upper bounds were computed by Lagrangean relaxation.