ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-09172021-093115


Thesis type
Tesi di laurea magistrale
Author
DI PASQUALE, FEDERICA
URN
etd-09172021-093115
Thesis title
A new Lagrangian approach to the Multiple Knapsack Assignment Problem
Department
INFORMATICA
Course of study
DATA SCIENCE AND BUSINESS INFORMATICS
Supervisors
relatore Frangioni, Antonio
Keywords
  • Optimization
  • Operations Research
  • MILP
  • Lagrangian Relaxation
  • SMS++
Graduation session start date
08/10/2021
Availability
Full
Summary
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