			Home About us Contact

Tree Problem (tree + problem)

Distribution by Scientific Domains

Mathematics and Statistics	81%

Selected Abstracts

An Explicit Solution of a Generalized Optimum Requirement Spanning Tree Problem With a Property Related to Monge

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2001
Tsutomu Anazawa
The paper considers a generalization of the optimum requirement spanning tree problem (ORST problem) first studied by Hu in 1974. Originally, ORST was regarded as a communication network of tree type with the minimum average cost, and it is obtained by the well-known Gomory,Hu algorithm when the degrees of vertices are not restricted. The ORST problem is generalized by (i) generalizing the objective function and (ii) imposing maximum degree constraints. The generalized ORST problem includes some practical problems, one of which is proposed in this paper, but is not efficiently solvable in general. However, I show that a particular tree (which is obtained by a sort of greedy algorithm but is explicitly definable) is a solution of the generalized problem when a certain practical condition is satisfied. The condition is closely related to the Monge property, which is originally discussed in the Hitchcock transportation problem, and is known to make some NP-hard problems efficiently solvable. [source]

Models and heuristics for a minimum arborescence problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2008
Christophe Duhamel
Abstract The Minimum Arborescence problem (MAP) consists of finding a minimum cost arborescence in a directed graph. This problem is NP-Hard and is a generalization of two well-known problems: the Minimum Spanning Arborescence Problem (MSAP) and the Directed Node Weighted Steiner Tree Problem (DNWSTP). We start the model presentation in this paper by describing four models for the MSAP (including two new ones, using so called "connectivity" constraints which forbid disconnected components) and we then describe the changes induced on the polyhedral structure of the problem by the removal of the spanning property. Only two (the two new ones) of the four models for the MSAP remain valid when the spanning property is removed. We also describe a multicommodity flow reformulation for the MAP that differs from well-known multicommodity flow reformulations in the sense that the flow conservation constraints at source and destination are replaced by inequalities. We show that the linear programming relaxation of this formulation is equivalent to the linear programming relaxation of the best of the two previous valid formulations and we also propose two Lagrangean relaxations based on the multicommodity flow reformulation. From the upper bound perspective, we describe a constructive heuristic as well as a local search procedure involving the concept of key path developed earlier for the Steiner Tree Problem. Numerical experiments taken from instances with up to 400 nodes are used to evaluate the proposed methods. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008 [source]

A comparative analysis of several formulations for the generalized minimum spanning tree problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2002
Corinne Feremans
Abstract This article describes eight formulations for the Generalized Minimum Spanning Tree Problem (GMSTP). Relationships between the polytopes of their linear relaxations are established. It is shown that four of these polytopes are strictly included in the remaining ones. This analysis suggests which formulations should be preferred for the construction of a branch-and-cut algorithm and for the evaluation of heuristics. © 2002 John Wiley & Sons, Inc. [source]

Network flow models for designing diameter-constrained minimum-spanning and Steiner trees

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2003
Luis Gouveia
Abstract We formulate and computationally test several models for the Diameter-Constrained Minimum Spanning and Steiner Tree Problems, which seek a least-cost spanning or Steiner tree subject to a (diameter) bound imposed on the number of edges in the tree between any node pair. A traditional multicommodity flow model with a commodity for every pair of nodes was unable to solve a 20-node and 100-edge spanning tree problem after 1 week of computation. In contrast, the new models were able to optimality solve this problem in less than 1 second and larger problem instances with up to 100 nodes and 1000 edges. The largest model contains more than 250,000 integer variables and more than 125,000 constraints. The new models simultaneously find a directed tree with a central node or a central edge that serve as a source for the commodities in a multicommodity flow model with hop constraints. Our results demonstrate the power of using single-sourcing combined with other reformulation techniques: directing the model and using hop-indexed formulations. Enhancements improve the models when the diameter bound is odd (these situations are more difficult to solve). The linear programming relaxation of the best formulations discussed in this paper always give an optimal integer solution for two special, polynomially solvable cases of the problem. © 2003 Wiley Periodicals, Inc. [source]

The Push Tree problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2004
Frédéric Havet
Abstract In this article, we introduce the Push Tree problem, which exposes the tradeoffs between the use of push and pull mechanisms in information distribution systems. One of the interesting features of the Push Tree problem is that it provides a smooth transition between the minimum Steiner Tree and the Shortest Path problems. We present initial complexity results and analyze heuristics. Moreover, we discuss what lessons can be learned from the static and deterministic Push Tree problem for more realistic scenarios characterized by high uncertainty and changing information request and update patterns. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 281,291 2004 [source]

An Explicit Solution of a Generalized Optimum Requirement Spanning Tree Problem With a Property Related to Monge

Very large-scale neighborhood search

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 4-5 2000
R.K. Ahuja
Abstract Neighborhood search algorithms are often the most effective approaches available for solving partitioning problems, a difficult class of combinatorial optimization problems arising in many application domains including vehicle routing, telecommunications network design, parallel machine scheduling, location theory, and clustering. A critical issue in the design of a neighborhood search algorithm is the choice of the neighborhood structure, that is, the manner in which the neighborhood is defined. Currently, the two-exchange neighborhood is the most widely used neighborhood for solving partitioning problems. The paper describes the cyclic exchange neighborhood, which is a generalization of the two-exchange neighborhood in which a neighbor is obtained by performing a cyclic exchange. The cyclic exchange neighborhood has substantially more neighbors compared to the two-exchange neighborhood. This paper outlines a network optimization based methodology to search the neighborhood efficiently and presents a proof of concept by applying it to the capacitated minimum spanning tree problem, an important problem in telecommunications network design. [source]

Noncooperative cost spanning tree games with budget restrictions

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 8 2008
Gustavo Bergantiños
Abstract We extend the noncooperative game associated with the cost spanning tree problem introduced by Bergantiños and Lorenzo (Math Method Oper Res 59(2004), 393,403) to situations where agents have budget restrictions. We study the Nash equilibria, subgame perfect Nash equilibria, and strong Nash equilibria of this game. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008 [source]

Approximation algorithm for the group Steiner network problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2007
Michal Penn
Abstract In this article we study the group Steiner network problem, which is defined in the following way. Given a graph G = (V,E), a partition of its vertices into K groups and connectivity requirements between the different groups, the aim is to find simultaneously a set of representatives, one for each group, and a minimum cost connected subgraph that satisfies the connectivity requirements between the groups (representatives). This problem is a generalization of the Steiner network problem and the group Steiner tree problem, two known NP-complete problems. We present an approximation algorithm for a special case of the group Steiner network problem with an approximation ratio of min {2(1 + 2x),2I}, where I is the cardinality of the largest group and x is a parameter that depends on the cost function. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(2), 160,167 2007 [source]

The sequential sum problem and performance bounds on the greedy algorithm for the on-line Steiner problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2005
Zevi Miller
Abstract This article is motivated by versions of the dynamic or "on-line" Steiner tree problem (OST) introduced by Imase and Waxman [4]. In this problem one is given an edge-weighted graph G and a sequence , = (x1,,,xn) of distinct vertices of G. The requirement is to construct for each i , n a tree Ti spanning the first i vertices of , subject to the condition that Ti,1,Ti for all i, where Ti is constructed without knowledge of the remaining vertices xj, j > i. The goal of the on-line Steiner problem is to minimize the performance ratio; that is, the maximum (over 1 , i , n) of the ratio of the weight of Ti to the weight of the minimum weight tree in G spanning the first i vertices (the latter tree is called the "Steiner tree" for these vertices). In [4] a lower bound of 1 + ½, log2(n,1), was proved for this ratio. The authors further made the interesting conjecture that there is some on-line algorithm for the OST whose performance ratio achieves this lower bound. We show that a strong form of the greedy algorithm achieves a ratio that converges to the conjectured ½log2(k) + O(1) as the proportion of degree 2 vertices in the instance graph grows. Our results also imply improvements in certain cases on the known upper bound ,log2(n), for the performance ratio of the greedy algorithm. Our approach is to study a related graph parameter. For each sequence , as above, define the associated cost where c(i,,) = min1 , t < idist(xi, xt). Then let Opt(n, G) be the maximum of L(,) over all such sequences , of length n. The problem of, given n and G, determining Opt(n, G) we call the Sequential Sum Problem (SSP). In this article we analyze the SSP, obtaining exact values and bounds on Opt(n, G) and relating these bounds to the greedy algorithm for the OST. For example, we calculate Opt(n, P) for the path P, and obtain a surprising characterization of all length n sequences , which realize Opt(n, P). By analyzing Opt(n, P) for the "continuous" path, we derive upper bounds on the performance ratio of the greedy algorithm for the OST in arbitrary graphs. On the other hand, generalizing the lower bound argument of [4] we show that there are instances of OST, which can significantly "fool" any on-line algorithm for OST. Specifically, given any tree T normalized to have total edge weight 1, we construct a graph G and a length k , |V(T)| sequence , of vertices of G for which the performance ratio of any on-line algorithm for the OST with input , is lower bounded by Opt(k, T). Finally, we show that the SSP for arbitrary G is NP-complete. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 143,164 2005 [source]

A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem,

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2003
Francisco Ortega
Abstract We present a branch-and-cut algorithm to solve the single-commodity, uncapacitated, fixed-charge network flow problem, which includes the Steiner tree problem, uncapacitated lot-sizing problems, and the fixed-charge transportation problem as special cases. The cuts used are simple dicut inequalities and their variants. A crucial problem when separating these inequalities is to find the right cut set on which to generate the inequalities. The prototype branch-and-cut system, bc,nd, includes a separation heuristic for the dicut inequalities and problem-specific primal heuristics, branching, and pruning rules. Computational results show that bc,nd is competitive compared to a variety of special purpose algorithms for problems with explicit flow costs. We also examine how general purpose MIP systems perform on such problems when provided with formulations that have been tightened a priori with dicut inequalities. © 2003 Wiley Periodicals, Inc. [source]

Network flow models for designing diameter-constrained minimum-spanning and Steiner trees

Preprocessing Steiner problems from VLSI layout

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2002
Eduardo Uchoa
Abstract VLSI layout applications yield instances of the Steiner tree problem over grid graphs with holes, which are considered hard to be solved by current methods. In particular, preprocessing techniques developed for Steiner problems over general graphs are not likely to reduce, significantly, such VLSI instances. We propose a new preprocessing procedure, extending earlier ideas from the literature and improving their application, so as to make them effective for VLSI problems. We report significant reductions within reasonable computational times, obtained with the application of this procedure to 116 instances of the SteinLib. These reductions allowed a branch and cut to solve 28 of 32 open instances of the SteinLib, some with more than 10,000 vertices and 20,000 edges. © 2002 Wiley Periodicals, Inc. [source]

A comparative analysis of several formulations for the generalized minimum spanning tree problem

Local search with perturbations for the prize-collecting Steiner tree problem in graphs

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2001
S. A. Canuto
Abstract Given an undirected graph with prizes associated with its nodes and weights associated with its edges, the prize-collecting Steiner tree problem consists of finding a subtree of this graph which minimizes the sum of the weights of its edges plus the prizes of the nodes not spanned. In this paper, we describe a multistart local search algorithm for the prize-collecting Steiner tree problem, based on the generation of initial solutions by a primal-dual algorithm using perturbed node prizes. Path-relinking is used to improve the solutions found by local search and variable neighborhood search is used as a post-optimization procedure. Computational experiments involving different algorithm variants are reported. Our results show that the local search with perturbations approach found optimal solutions on nearly all of the instances tested. © 2001 John Wiley & Sons, Inc. [source]