Abstract
Abstract This paper studies the generalized hop-constrained minimum spanning tree problem (GHMSTP) which has applications in backbone network design subject to quality-of-service constraints that restrict the maximum number of intermediate routers along each communication path. Different possibilities to model the GHMSTP as an integer linear program and strengthening valid inequalities are studied. The obtained formulations are compared theoretically, i.e., by means of their linear programming relaxation. In addition, branch-and-cut approaches based on these formulations are developed and compared in a computational study.
| Original language | English |
|---|---|
| Article number | 3812 |
| Pages (from-to) | 1-18 |
| Number of pages | 18 |
| Journal | Computers and Operations Research |
| Volume | 65 |
| DOIs | |
| Publication status | Published - 18 Jul 2016 |
| Externally published | Yes |
Funding
This work has been supported by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office and the Austrian Science Fund (FWF) under grant I892-N23 . These supports are greatly acknowledged.
Keywords
- Branch-and-cut
- Generalized network design
- Hop-constraints
- Integer programming
- Layered graph