We propose an iterative memory-based algorithm for solving a class of combinatorial optimization problems. The algorithm generates a sequence of gradually improving solutions by exploiting at each iteration the knowledge gained in previous iterations. At each iteration, the algorithm builds an enumerative tree and stores at each tree level a set of promising partial solutions that will be used to drive the tree exploration in the following iteration. We tested the effectiveness of the proposed method on an hard combinatorial optimization problem arising in the design of telecommunication networks, the Non Bifurcated Network Design Problem, and we report computational results on a set of test problems simulating real life instances.
E. Bartolini, V. Maniezzo, A. Mingozzi (2008). An Adaptive Memory-Based Approach Based on Partial Enumeration. BERLIN : Springer-Verlag [10.1007/978-3-540-92695-5_2].
An Adaptive Memory-Based Approach Based on Partial Enumeration
BARTOLINI, ENRICO;MANIEZZO, VITTORIO;MINGOZZI, ARISTIDE
2008
Abstract
We propose an iterative memory-based algorithm for solving a class of combinatorial optimization problems. The algorithm generates a sequence of gradually improving solutions by exploiting at each iteration the knowledge gained in previous iterations. At each iteration, the algorithm builds an enumerative tree and stores at each tree level a set of promising partial solutions that will be used to drive the tree exploration in the following iteration. We tested the effectiveness of the proposed method on an hard combinatorial optimization problem arising in the design of telecommunication networks, the Non Bifurcated Network Design Problem, and we report computational results on a set of test problems simulating real life instances.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
