Memorization, as an algorithm design technique, enables to speed up algorithms at the price of increased space usage. In this work, we focus on search tree algorithms applied to sequencing problems. In these algorithms, on lower branching levels, isomorphic sub-problems may appear exponentially many times and the use of memorization is twofold: on the one hand it avoids repetitive solutions, as they correspond to identical sub-problems; on the other hand, it allows to check for dominance conditions among permutations of the same subset of elements. The idea of memorization appeared for a long time, however, to the best of the authors’ knowledge, it was only seldom applied in the number of branching algorithms proposed in the literature. In this paper, we propose a unifying framework for implementing memorization in exact branching algorithms dedicated to sequencing problems. Our proposal leads to the paradigm of Branch & Memorize and its implementation to three classical single machine problems is validated by an extensive computational experimentation that shows that the mentioned paradigm consistently improves existing exact branching algorithms. These results emphasize the idea of more systematically embedding memorization in branching algorithms.

Branch & Memorize exact algorithms for sequencing problems: Efficient embedding of memorization into search trees / Shang, L.; T'Kindt, V.; Della Croce, F.. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - ELETTRONICO. - 128:(2021), p. 105171. [10.1016/j.cor.2020.105171]

Branch & Memorize exact algorithms for sequencing problems: Efficient embedding of memorization into search trees

T'Kindt V.;Della Croce F.
2021

Abstract

Memorization, as an algorithm design technique, enables to speed up algorithms at the price of increased space usage. In this work, we focus on search tree algorithms applied to sequencing problems. In these algorithms, on lower branching levels, isomorphic sub-problems may appear exponentially many times and the use of memorization is twofold: on the one hand it avoids repetitive solutions, as they correspond to identical sub-problems; on the other hand, it allows to check for dominance conditions among permutations of the same subset of elements. The idea of memorization appeared for a long time, however, to the best of the authors’ knowledge, it was only seldom applied in the number of branching algorithms proposed in the literature. In this paper, we propose a unifying framework for implementing memorization in exact branching algorithms dedicated to sequencing problems. Our proposal leads to the paradigm of Branch & Memorize and its implementation to three classical single machine problems is validated by an extensive computational experimentation that shows that the mentioned paradigm consistently improves existing exact branching algorithms. These results emphasize the idea of more systematically embedding memorization in branching algorithms.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0305054820302884-main.pdf

non disponibili

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 728.54 kB
Formato Adobe PDF
728.54 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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/11583/2948114