This paper presents a short (and not exhaustive) introduction to the most used exact, approximation, and metaheuristic algorithms for solving hard combinatorial optimization problems. After introducing the basics of exact approaches such as Branch & Bound and Dynamic Programming, we focus on the basics of the most studied approximation techniques and of the most applied algorithms for nding good suboptimal solutions, including genetic algorithms, simulated annealing, tabu search, variable neighborhood search, greedy randomized adaptive search procedures (GRASP), path relinking, and scatter search.

A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems2014 16th International Conference on Transparent Optical Networks (ICTON)

FESTA, PAOLA
2014

Abstract

This paper presents a short (and not exhaustive) introduction to the most used exact, approximation, and metaheuristic algorithms for solving hard combinatorial optimization problems. After introducing the basics of exact approaches such as Branch & Bound and Dynamic Programming, we focus on the basics of the most studied approximation techniques and of the most applied algorithms for nding good suboptimal solutions, including genetic algorithms, simulated annealing, tabu search, variable neighborhood search, greedy randomized adaptive search procedures (GRASP), path relinking, and scatter search.
9781479956012
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11588/586780
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? ND
social impact