logo SBA

ETD

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

Tesi etd-09122022-144753


Tipo di tesi
Tesi di laurea magistrale
Autore
CUDAZZO, ALESSANDRO
URN
etd-09122022-144753
Titolo
Towards a Branch-and-Cut Algorithm for Lexicographic Multi-Objective Mixed-Integer Linear Programming
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof. Pappalardo, Massimo
correlatore Prof. Cococcioni, Marco
Parole chiave
  • Grossone methodology
  • integer linear programming
  • lexicographic optimization
  • mixed integer linear programming
  • multi-objective optimization
  • numerical infinitesimals
Data inizio appello
07/10/2022
Consultabilità
Non consultabile
Data di rilascio
07/10/2092
Riassunto
The first aim was to extend the GrossBB in order to support the GrossDualSimplex. This leads to an efficient implementation of the GrossBB for solving LMOMILP (Lexicographic Multi-Objective Mixed-Integer Linear Programming) problems by exploiting and adapting the optimal dual basis found in a previous node, by the GrossDualSimplex, which is still feasible for the dual problem of the subsequent node. Next, we investigated solving LMOILP (Lexicographic Multi-Objective Integer Linear Programming) problems by exploiting Gomory Fractional Cuts and the Objective Function Gomory cut in a scenario in which non-Archimedean components are involved. This resulted in a new set of cutting plans for LMOILP problems, which we called Gross Objective Function Gomory cuts, consisting of cutting plan inspired by each fractional objective function that composes the multi-objective problem. Finally, a new algorithm for LMOILP problems, called Gross Gomory's lexicographic cutting plane method, was presented, which is able to converge to the optimal integer solution by applying cutting planes with an appropriate lexicographic rule.
File