• PDF / 14,725,564 Bytes
• 149 Pages / 594 x 828 pts Page_size
• 74 Downloads / 276 Views

DOWNLOAD

REPORT

---

unit weight CMST or equal demand CMST; otherwise it is called the nonunit weight case. Most references in the literature deal with the unit weight case with only a few exceptions treating the more general case. For a comprehensive survey of the (unit weight) CMST up to the mid-1990s see [4]. The CMST in undirected graphs requires a symmetric cost matrix. Otherwise, the direction of the arcs has to be considered, i.e., all subtrees are directed. This capacitated minimum spanning arborescence problem (CMDT) includes the CMST as a special case. Motivated by the intractability of the problem both heuristic as well as exact algorithms have been developed. In the sequel various algorithmic concepts are reviewed mainly for the unit weight CMST (with special emphasis on progress made in the late nineties; for some older yet important references not given here see [4]). However, first we sketch some applications of the CMST some of which may also lead to important modifications of the problem. A p p l i c a t i o n s . The CMST has a great variety of applications especially in the field of telecommunications network design. For instance, in the design of minimum cost teleprocessing networks terminals (nodes) have to be connected to a central facility (the center node) by so-called multipoint lines (the subtrees) which have to be restricted with respect to the traffic transfered between the center and the included terminals or the number of terminals included in the line. The latter is sometimes called reliability constraint because it limits the maximal number of terminals disconnected from the central

Capacitated minimum spanning trees

facility in the case of a single link breakdown. Although different constraints may be referred to as capacity constraints (e.g. considering arc weights instead of node weights or even nonlinear weight functions depending on the distance of a node or arc from the center) most formulations in the literature consider only one of them.

Mathematical Programming Formulations. For the CMST a great variety of formulations may be found in the literature; see, e.g., [14], [19], [20], [21], [22]. Here we restrict ourselves to the presentation of a well-known flow-based formulation. As relaxations of directed formulations may be advantageous we consider the CMDT. Assume bi = 1 for all i = 1 , . . . , n , and b0 = 0, then the CMDT can be described as a mixed integer linear programming formulation as follows. Define xij = 1, if arc (i, j) is included in the solution, and xij = O, otherwise. Furthermore, let Yij denote the flow on arc (i, j) for all i, j, i.e., i = 0 , . . . , n and j = 1 , . . . , n . Ensure variables xij and Yij with (i, j) ~ A to be equal to zero by assigning prohibitively large weights to them. The following single-commodity flow formulation gives a minimum cost directed capacitated spanning tree with center node 0 as the root: n

n

min i=0 j = l n

s.t.

xij = l,

j-1,...,n,

i=0 n

n

(P)

-

i=0 j--

-

1,

i=1 1,...,n~

xij < Yij < ( K -

bi).xij

for all i, j, ,

xij E {0, 1