Heuristics for the solution of Mixed-Integer Linear Programming problems
Lorenzo Bonasera
Heuristics for the solution of Mixed-Integer Linear Programming problems.
Rel. Paolo Brandimarte. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2021
|
Preview |
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (2MB) | Preview |
Abstract
Many discrete optimization problems can be reframed as Integer Linear Programming (ILP) problems, whose complexity class is NP-Hard. Due to its NP-hardness, solving a ILP problem to optimality often requires a huge computational effort. Therefore it’s necessary to adopt greedy algorithms and heuristics that are capable of finding satisfying solutions at a lower cost. The most common heuristics don’t require a mathematical model and they are based on local search, e.g. tabu search, or population search, like genetic algorithms or particle swarm optimization. Those heuristics are not easy to apply in case of complicated constraints and/or when dealing with optimization problems that contain both continuous and discrete decision variables, known as Mixed-Integer Linear Programming (MILP) problems, hence the need of more adaptable and general heuristics.
Thus, different algorithms have been proposed, like fix-and-relax, iterated local search and kernel search, based on mathematical models which impose proper forms of restriction on decision variables
Relatori
Tipo di pubblicazione
URI
![]() |
Modifica (riservato agli operatori) |
