• Optimization
• Operations Research
• MILP
• Lagrangian Relaxation
• SMS++

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.