We study a variant of the spanning tree problem where we require that, for a given connected graph, the spanning tree to be found has the minimum number of branch vertices (that is vertices of the tree whose degree is greater than two). We provide four different formulations of the problem and compare different relaxations of them, namely Lagrangian relaxation, continuous relaxation, mixed integer-continuous relaxation. We approach the solution of the Lagrangian dual both by means of a standard subgradient method and an ad-hoc finite ascent algorithm based on updating one multiplier at the time. We provide numerical result comparison of all the considered relaxations on a wide set of benchmark instances. A useful follow-up of tackling the Lagrangian dual is the possibility of getting a feasible solution for the original problem with no extra costs. We evaluate the quality of the resulting upper bound by comparison either with the optimal solution, whenever available, or with the feasible solution provided by some existing heuristic algorithms.

Lower and upper bounds for the spanning tree with minimum branch vertices

CARRABS, FRANCESCO;CERULLI, Raffaele;GENTILI, Monica
2013

Abstract

We study a variant of the spanning tree problem where we require that, for a given connected graph, the spanning tree to be found has the minimum number of branch vertices (that is vertices of the tree whose degree is greater than two). We provide four different formulations of the problem and compare different relaxations of them, namely Lagrangian relaxation, continuous relaxation, mixed integer-continuous relaxation. We approach the solution of the Lagrangian dual both by means of a standard subgradient method and an ad-hoc finite ascent algorithm based on updating one multiplier at the time. We provide numerical result comparison of all the considered relaxations on a wide set of benchmark instances. A useful follow-up of tackling the Lagrangian dual is the possibility of getting a feasible solution for the original problem with no extra costs. We evaluate the quality of the resulting upper bound by comparison either with the optimal solution, whenever available, or with the feasible solution provided by some existing heuristic algorithms.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/4036853
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 24
social impact