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 language | English |
---|---|
Pages (from-to) | 322-332 |
Number of pages | 11 |
Journal | Computers and Operations Research |
Volume | 81 |
DOIs | |
Publication status | Published - 1 May 2017 |
Keywords
- Branch vertices
- Branch-and-cut
- Spanning tree
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research