logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-09172021-093115


Tipo di tesi
Tesi di laurea magistrale
Autore
DI PASQUALE, FEDERICA
URN
etd-09172021-093115
Titolo
A new Lagrangian approach to the Multiple Knapsack Assignment Problem
Dipartimento
INFORMATICA
Corso di studi
DATA SCIENCE AND BUSINESS INFORMATICS
Relatori
relatore Frangioni, Antonio
Parole chiave
  • Lagrangian Relaxation
  • MILP
  • Operations Research
  • Optimization
  • SMS++
Data inizio appello
08/10/2021
Consultabilità
Completa
Riassunto
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.
File