Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem |
| |
Authors: | Babacar Thiongane Anass Nagih Gérard Plateau |
| |
Institution: | Laboratoire d’Informatique de Paris Nord, UMR CNRS 7030, Université de Paris 13, 99, avenue Jean-Baptiste Clément, 93430 Villetaneuse, France |
| |
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. |
| |
Keywords: | 0-1 Knapsack Lagrangean relaxation Subgradient algorithm Local search Reoptimization |
本文献已被 ScienceDirect 等数据库收录! |
|