Article ID: | iaor2006994 |
Country: | Netherlands |
Volume: | 139 |
Issue: | 1 |
Start Page Number: | 353 |
End Page Number: | 373 |
Publication Date: | Oct 2005 |
Journal: | Annals of Operations Research |
Authors: | Plateau Grard, Nagih Anass, Thiongane Babacar |
Keywords: | knapsack problem, duality |
This paper deals with a new algorithm for a 0–1 bidimensional knapsack Lagrangean dual which relaxes one of the two constraints. Classical iterative algorithms generate a sequence of multipliers which converges to an optimal one. In this way, these methods generate a sequence of 0–1 one-dimensional knapsack instances. Generally, the procedure for solving each instance is considered as a black box. We propose to design a new iterative scheme in which the computation of the step size takes into account the algorithmic efficiency of each instance. Our adapted step size iterative algorithm is compared favorably with several other algorithms for the 0–1 biknapsack Lagrangean dual over difficult instances for CPLEX 7.0.