Algorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem |
| |
Authors: | José Rui Figueira Luís Paquete Marco Simões Daniel Vanderpooten |
| |
Affiliation: | 1. CEG-IST, Center for Management Studies, Instituto Superior Técnico, Technical University of Lisbon, TagusPark, Av. Cavaco Silva, 2780-990, Porto Salvo, Portugal 2. CISUC, Department of Informatics Engineering, University of Coimbra, Pólo II, 3030-290, Coimbra, Portugal 3. University Paris-Dauphine, LAMSADE, Place du Marechal de Lattre de Tassigny, 75775, Paris Cedex 16, France
|
| |
Abstract: | This paper presents several methodological and algorithmic improvements over a state-of-the-art dynamic programming algorithm for solving the bi-objective {0,1} knapsack problem. The variants proposed make use of new definitions of lower and upper bounds, which allow a large number of states to be discarded. The computation of these bounds are based on the application of dichotomic search, definition of new bound sets, and bi-objective simplex algorithms to solve the relaxed problem. Although these new techniques are not of a common application for dynamic programming, we show that the best variants tested in this work can lead to an average improvement of 10 to 30 % in CPU-time and significant less memory usage than the original approach in a wide benchmark set of instances, even for the most difficult ones in the literature. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|