An adapted step size algorithm for a 0–1 biknapsack Lagrangean dual

An adapted step size algorithm for a 0–1 biknapsack Lagrangean dual

0.00 Avg rating0 Votes
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: , ,
Keywords: knapsack problem, duality
Abstract:

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.

Reviews

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