A branch-and-cut algorithm for the minimum branch vertices spanning tree problem

Selene Silvestri, Gilbert Laporte, Raffaele Cerulli

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

Given a connected undirected graph G=(V,E), the Minimum Branch Vertices Problem (MBVP) asks for a spanning tree of G with the minimum number of vertices having degree greater than two in the tree. These are called branch vertices. This problem, with applications in the context of optical networks, is known to be NP-hard. We model the MBVP as an integer linear program, with undirected variables, we derive valid inequalities and we prove that some of these are facet defining. We then develop a hybrid formulation containing undirected and directed variables. Both models are solved with branch-and-cut. Comparative computational results show the superiority of the hybrid formulation.

Original languageEnglish
Pages (from-to)322-332
Number of pages11
JournalComputers and Operations Research
Volume81
DOIs
Publication statusPublished - 1 May 2017

Keywords

  • Branch vertices
  • Branch-and-cut
  • Spanning tree

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A branch-and-cut algorithm for the minimum branch vertices spanning tree problem'. Together they form a unique fingerprint.

Cite this