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.

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.
Learning and Intelligent Optimization
12
24
E. Bartolini; V. Maniezzo; A. Mingozzi
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/65509
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact