Politecnico di Torino (logo)

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

PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (2MB) | Preview

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. This work aims to investigate and apply the kernel search framework on a specific case of study, in order to propose a reliable and well-performing problem-specific variation of the heuristic. The chosen case study is a stochastic version of the classical multi-item Capacitated Lot-Sizing Problem (CLSP), in which demand uncertainty is modelled through a scenario tree, resulting in a multi-stage mixed-integer stochastic programming model.

Relators: Paolo Brandimarte
Academic year: 2021/22
Publication type: Electronic
Number of Pages: 51
Corso di laurea: Corso di laurea magistrale in Ingegneria Matematica
Classe di laurea: New organization > Master science > LM-44 - MATHEMATICAL MODELLING FOR ENGINEERING
Aziende collaboratrici: UNSPECIFIED
URI: http://webthesis.biblio.polito.it/id/eprint/19857
Modify record (reserved for operators) Modify record (reserved for operators)