## 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

### Refine

#### Keywords

- Adjazenz-Beziehungen (1)
- Knapsack (1)
- Kombinatorische Optimierung (1)
- Minimal spannender Baum (1)
- adjacency relations (1)
- combinatorial optimization (1)
- knapsack (1)
- minimal spanning tree (1)

- Weight-Constrained Minimum Spanning Tree Problem (2007)
- In an undirected graph G we associate costs and weights to each edge. The weight-constrained minimum spanning tree problem is to find a spanning tree of total edge weight at most a given value W and minimum total costs under this restriction. In this thesis a literature overview on this NP-hard problem, theoretical properties concerning the convex hull and the Lagrangian relaxation are given. We present also some in- and exclusion-test for this problem. We apply a ranking algorithm and the method of approximation through decomposition to our problem and design also a new branch and bound scheme. The numerical results show that this new solution approach performs better than the existing algorithms.