Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420989 | Discrete Applied Mathematics | 2006 | 12 Pages |
Abstract
First, this paper deals with lagrangean heuristics for the 0–1 bidimensional knapsack problem. A projected subgradient algorithm is performed for solving a lagrangean dual of the problem, to improve the convergence of the classical subgradient algorithm. Secondly, a local search is introduced to improve the lower bound on the value of the biknapsack produced by lagrangean heuristics. Thirdly, a variable fixing phase is embedded in the process. Finally, the sequence of 0–1 one-dimensional knapsack instances obtained from the algorithm are solved by using reoptimization techniques in order to reduce the total computational time effort. Computational results are presented.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Babacar Thiongane, Anass Nagih, Gérard Plateau,