Loading...
Please wait, while we are loading the content...
Similar Documents
Branch-and-Price for the Steiner Tree Problem with Revenues , Budget and Hop Constraints
| Content Provider | Semantic Scholar |
|---|---|
| Author | Sinnl, Markus Arbeit, Verfassung Der |
| Copyright Year | 2011 |
| Abstract | This thesis deals with the Steiner tree problem with revenues, budget and hop constraints (STPRBH), an NP-hard combinatorial optimization problem with applications in telecommunications network design. An instance of the STPRBH is defined by a connected graph with a dedicated root node, a set of nodes with nonnegative revenues and positive costs assigned to edges. Furthermore, a budgetB ≥ 0 and a hop limitH ∈ N are given. The set of feasible solutions is given by all Steiner trees containing the root node, where every path from the root node to any other node in the tree contains at most H edges. Furthermore, the total edge costs of such a tree must be lower or equal to the given budget B. The goal is to find a feasible solution with maximum revenue, i.e. to maximize the sum of revenues associated with nodes which are part of the solution. Several formulations for the STPRBH based on integer linear programming using exponentially many variables are presented. Furthermore, branch-and-price approaches based on these formulations are introduced that allow for solving instances of the STPRBH to proven optimality. The practical implementations of these branch-and-price approaches do, however, suffer from various problems. Thus, the applicability of various attempts to improve their efficiency like stabilization techniques, different pricing strategies and heuristic methods to generate initial solutions is analyzed. Furthermore, promising methods are correspondingly adapted and applied to the STPRBH. Tests on previously existing benchmark instances show that the presented branch-and-price approaches are competitive with existing exact methods based on branch-and-cut when the hop limit is rather restrictive or if the number of nodes with positive revenue is relatively small. Furthermore, when the budget B does not play a role (i.e. is high enough to pose no restriction), branch-and-price usually outperforms branch-and-cut. It should be noted, however, that this specific variant of the STPRBH is not NP -hard. For instances with a large hop limit or a large number of nodes with positive revenue the proposed branch-and-price approaches are not yet competitive to branch-and-cut. Due to the implemented stabilization and acceleration methods a significant speed-up of branch-and-price has, however, been achieved for these instances too. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://publik.tuwien.ac.at/files/PubDat_200753.pdf |
| Alternate Webpage(s) | https://publik.tuwien.ac.at/files/PubDat_200753.pdf |
| Alternate Webpage(s) | https://www.ac.tuwien.ac.at/files/pub/sinnl-11.pdf |
| Alternate Webpage(s) | https://www.ads.tuwien.ac.at/publications/bib/pdf/sinnl-11.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
