A BRIEF INTRODUCTION TO EXACT, APPROXIMATION, AND HEURISTIC ALGORITHMS FOR SOLVING HARD COMBINATORIAL OPTIMIZATION PROBLEMS

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 finding good suboptimal solutions, including genetic algorithms, simulated annealing, tabu search, variable neighborhood search, greedy randomized adaptive search procedures (GRASP), path relinking, and scatter search.