Lagrangean methods for the 0–1 Quadratic Knapsack

Lagrangean methods for the 0–1 Quadratic Knapsack

0.00 Avg rating0 Votes
Article ID: iaor1999389
Country: Netherlands
Volume: 92
Issue: 2
Start Page Number: 326
End Page Number: 341
Publication Date: Jul 1996
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: quadratic
Abstract:

It is well known that the Lagrangean decomposition provides better bounds than the Lagrangean relaxation does. Nevertheless, the Lagrangean decomposition bound is harder to compute than the Lagrangean relaxation 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 study the Lagrangean decomposition for this problem and give new necessary optimality conditions for the dual problem which allow us to elaborate a heuristic method for solving the Lagrangean decomposition duel problem. We then introduce this method in Chaillou–Hansen–Mahieu's branch-and-bound algorithm where upper bounds were computed by Lagrangean relaxation.

Reviews

Required fields are marked *. Your email address will not be published.