ETD

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

Tesi etd-06252020-195454


Tipo di tesi
Tesi di laurea magistrale
Autore
MASTROCINQUE, ANGELA
URN
etd-06252020-195454
Titolo
Primal stabilization in column generation
Dipartimento
MATEMATICA
Corso di studi
MATEMATICA
Relatori
relatore Prof. Frangioni, Antonio
controrelatore Prof.ssa Galli, Laura
Parole chiave
  • generation
  • column
  • stabilization
  • primal
Data inizio appello
10/07/2020
Consultabilità
Completa
Riassunto
In the framework of column generation algorithms for Integer Lin- ear Programs, we propose a stabilization method which acts directly on the primal variables. This amounts to developing heuristics to force the pricer to generate “good” columns, in order to diminish the tailing-off effect which is typical to column generations applied to large-scale instances. We propose a method of “suggesting elements”, i.e. of checking the quality of a column based on some criteria: the pricer will then give higher priority to good columns. We apply this technique to the Bin Packing Problem and to the Capacitated Vehicle Routing Problem, and report the results of the relative numerical experiments, which we conduct using the solver SCIP. The heuristics in the two cases are Dantzig’s greedy algorithm and a suggesting technique used by MAIOR company respectively. In particular, we find that the results are promising in both cases, although the precise set- tings of the parameters which significantly and systematically improve the algorithm have yet to be found.
File