logo SBA

ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-06252020-195454


Thesis type
Tesi di laurea magistrale
Author
MASTROCINQUE, ANGELA
URN
etd-06252020-195454
Thesis title
Primal stabilization in column generation
Department
MATEMATICA
Course of study
MATEMATICA
Supervisors
relatore Prof. Frangioni, Antonio
controrelatore Prof.ssa Galli, Laura
Keywords
  • column
  • generation
  • primal
  • stabilization
Graduation session start date
10/07/2020
Availability
Full
Summary
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