Tipo di tesi
Tesi di laurea magistrale
Titolo
A new Lagrangian approach to the Multiple Knapsack Assignment Problem
Corso di studi
DATA SCIENCE AND BUSINESS INFORMATICS
Parole chiave
- Lagrangian Relaxation
- MILP
- Operations Research
- Optimization
- SMS++
Data inizio appello
08/10/2021
Riassunto (Italiano)
Mixed Integer Linear Programming (MILP) problems are widely used in many real-world situations, but they are also almost always difficult to solve. In this Thesis, the focus is on the problem of estimating an upper bound on the optimal value of a MILP, taking as a case study the recently introduced Multiple Knapsack Assignment Problem (MKAP), for which we propose a new Lagrangian Relaxation approach. The MKAP has been modeled through a Structured Modeling System, SMS++, which provides the required solvers to compute the Lagrangian Relaxation bound; however, some necessary SMS++ components were not yet present, so most of this Thesis work includes their development. Finally, computational experiments conducted on some literature instances allowed for an evaluation of the effectiveness of the proposed approach.
