共查询到20条相似文献,搜索用时 15 毫秒
1.
We introduce the prize-collecting generalized minimum spanning tree problem. In this problem a network of node clusters needs
to be connected via a tree architecture using exactly one node per cluster. Nodes in each cluster compete by offering a payment
for selection. This problem is NP-hard, and we describe several heuristic strategies, including local search and a genetic
algorithm. Further, we present a simple and computationally efficient branch-and-cut algorithm. Our computational study indicates
that our branch-and-cut algorithm finds optimal solutions for networks with up to 200 nodes within two hours of CPU time,
while the heuristic search procedures rapidly find near-optimal solutions for all of the test instances. 相似文献
2.
P. C. Pop 《Annals of Operations Research》2007,150(1):193-204
The prize-collecting generalized minimum spanning tree problem (PC-GMSTP), is a generalization of the generalized minimum
spanning tree problem (GMSTP) and belongs to the hard core of -hard problems. We describe an exact exponential time algorithm for the problem, as well we present several mixed integer and integer
programming formulations of the PC-GMSTP. Moreover, we establish relationships between the polytopes corresponding to their
linear relaxations and present an efficient solution procedure that finds the optimal solution of the PC-GMSTP for graphs
with up 240 nodes. 相似文献
3.
The 2-rooted mini-max spanning forest problem is to find a spanning forest with two given root nodes on an undirected graph, such that the maximum tree cost in this forest is minimized. We introduce a branch-and-bound algorithm based on selecting nodes. On test instances up to 50 nodes the algorithm gives much better computational results than a known algorithm that is based on selecting edges. Furthermore the new algorithm can easily solve problem instances up to 80 nodes. 相似文献
4.
《European Journal of Operational Research》2020,280(1):46-58
In this paper, we investigate Semidefinite Programming (SDP) lower bounds for the Quadratic Minimum Spanning Tree Problem (QMSTP). Two SDP lower bounding approaches are introduced here. Both apply Lagrangian Relaxation to an SDP relaxation for the problem. The first one explicitly dualizes the semidefiniteness constraint, attaching to it a positive semidefinite matrix of Lagrangian multipliers. The second relies on a semi-infinite reformulation for the cone of positive semidefinite matrices and dualizes a dynamically updated finite set of inequalities that approximate the cone. These lower bounding procedures are the core ingredient of two QMSTP Branch-and-bound algorithms. Our computational experiments indicate that the SDP bounds computed here are very strong, being able to close at least 70% of the gaps of the most competitive formulation in the literature. As a result, their accompanying Branch-and-bound algorithms are competitive with the best previously available QMSTP exact algorithm in the literature. In fact, one of these new Branch-and-bound algorithms stands out as the new best exact solution approach for the problem. 相似文献
5.
Corinne Feremans Alexander Grigoriev René Sitters 《4OR: A Quarterly Journal of Operations Research》2006,4(4):319-329
This paper is concerned with a special case of the generalized minimum spanning tree problem. The problem is defined on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to find a tree of minimum cost containing at least one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance defines the edge cost. We prove that the problem is strongly
-hard even in the case of a special structure of the clustering called grid clustering. We construct an exact exponential time dynamic programming algorithm and, based on this dynamic programming algorithm, we develop a polynomial time approximation scheme for the problem with grid clustering. 相似文献
6.
This paper describes an attribute based tabu search heuristic for the generalized minimum spanning tree problem (GMSTP) known to be NP-hard. Given a graph whose vertex set is partitioned into clusters, the GMSTP consists of designing a minimum cost tree spanning all clusters. An attribute based tabu search heuristic employing new neighborhoods is proposed. An extended set of TSPLIB test instances for the GMSTP is generated and the heuristic is compared with recently proposed genetic algorithms. The proposed heuristic yields the best results for all instances. Moreover, an adaptation of the tabu search algorithm is proposed for a variation of the GMSTP in which each cluster must be spanned at least once. 相似文献
7.
8.
《European Journal of Operational Research》1999,114(1):141-152
Minimum Spanning Tree (MST) problem is of high importance in network optimization. The multi-criteria MST (mc-MST) is a more realistic representation of the practical problem in the real world, but it is difficult for the traditional network optimization technique to deal with. In this paper, a genetic algorithm (GA) approach is developed to deal with this problem. Without neglecting its network topology, the proposed method adopts the Prüfer number as the tree encoding and applies the Multiple Criteria Decision Making (MCDM) technique and nondominated sorting technique to make the GA search give out all Pareto optimal solutions either focused on the region near the ideal point or distributed all along the Pareto frontier. Compared with the enumeration method of Pareto optimal solution, the numerical analysis shows the efficiency and effectiveness of the GA approach on the mc-MST problem. 相似文献
9.
10.
José Elias Claudio Arroyo Pedro Sampaio Vieira Dalessandro Soares Vianna 《Annals of Operations Research》2008,159(1):125-133
This paper proposes a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm for the multi-criteria minimum spanning
tree problem, which is NP-hard. In this problem a vector of costs is defined for each edge of the graph and the problem is
to find all Pareto optimal or efficient spanning trees (solutions). The algorithm is based on the optimization of different
weighted utility functions. In each iteration, a weight vector is defined and a solution is built using a greedy randomized
constructive procedure. The found solution is submitted to a local search trying to improve the value of the weighted utility
function. We use a drop-and-add neighborhood where the spanning trees are represented by Prufer numbers. In order to find a variety of efficient solutions,
we use different weight vectors, which are distributed uniformly on the Pareto frontier.
The proposed algorithm is tested on problems with r=2 and 3 criteria. For non-complete graphs with n=10, 20 and 30 nodes, the performance of the algorithm is tested against a complete enumeration. For complete graphs with
n=20, 30 and 50 nodes the performance of the algorithm is tested using two types of weighted utility functions. The algorithm
is also compared with the multi-criteria version of the Kruskal’s algorithm, which generates supported efficient solutions.
This work was funded by the Municipal Town Hall of Campos dos Goytacazes city. The used computer was acquired with resource
of CNPq. 相似文献
11.
12.
《European Journal of Operational Research》1997,101(1):93-103
The mini-max spanning forest problem requires to find a spanning forest of an undirected graph that minimizes the maximum of the costs of constituent trees. In a previous work we proved this problem NP-hard. In the current paper we present three lower bounds for this problem and develop a branch-and-bound algorithm to solve the problem exactly. The algorithm is implemented and numerical experiments are conducted on a series of test problems. The experiments compare the performances of the proposed bounds and search strategies in the algorithm as well as investigate the effects of instance characteristics on the behavior of the algorithm. Also, extension of the problem to the case of more than two root vertices as well as to the problem of determining the root locations are discussed. 相似文献
13.
Evolutionary algorithms are applied to problems that are not well understood as well as to problems in combinatorial optimization. The analysis of these search heuristics has been started for some well-known polynomial solvable problems. Such analyses are starting points for the analysis of evolutionary algorithms on difficult problems. We present the first runtime analysis of a multi-objective evolutionary algorithm on a NP-hard problem. The subject of our analysis is the multi-objective minimum spanning tree problem for which we give upper bounds on the expected time until a simple evolutionary algorithm has produced a population including for each extremal point of the Pareto front a corresponding spanning tree. These points are of particular interest as they give a 2-approximation of the Pareto front. We show that in expected pseudopolynomial time a population is produced that includes for each extremal point a corresponding spanning tree. 相似文献
14.
This paper introduces dual and primal-dual RAMP algorithms for the solution of the capacitated minimum spanning tree problem
(CMST). A surrogate constraint relaxation incorporating cutting planes is proposed to explore the dual solution space. In
the dual RAMP approach, primal-feasible solutions are obtained by simple tabu searches that project dual solutions onto primal
feasible space. A primal-dual approach is achieved by including a scatter search procedure that further exploits the adaptive
memory framework. Computational results from applying the methods to a standard set of benchmark problems disclose that the
dual RAMP algorithm finds high quality solutions very efficiently and that its primal-dual enhancement is still more effective. 相似文献
15.
16.
A.M. Frieze 《Discrete Applied Mathematics》1985,10(1):47-56
Suppose we are given a complete graph on n vertices in which the lenghts of the edges are independent identically distributed non-negative random variables. Suppose that their common distribution function F is differentiable at zero and D = F′ (0) > 0 and each edge length has a finite mean and variance. Let Ln be the random variable whose value is the length of the minimum spanning tree in such a graph. Then we will prove the following: limn → ∞E(Ln) = ζ(3)/D where ζ(3) = Σk = 1∞ 1/k3 = 1.202… and for any ε > 0 limn → ∞ Pr(|Ln?ζ(3)/D|) > ε) = 0. 相似文献
17.
Oleksii Ursulenko Sergiy Butenko Oleg A. Prokopyev 《Journal of Global Optimization》2013,56(3):1029-1043
This paper studies the sum-of-ratios version of the classical minimum spanning tree problem. We describe a branch-and-bound algorithm for solving the general version of the problem based on its image space representation. The suggested approach specifically addresses the difficulties arising in the case when the number of ratios exceeds two. The efficacy of our approach is demonstrated on randomly generated complete and sparse graph instances. 相似文献
18.
Christos A. Pappas Angelos-Christos G. Anadiotis Chrysa A. Papagianni Iakovos S. Venieris 《Optimization Letters》2014,8(2):435-446
The capacitated minimum spanning tree (CMST) problem is fundamental to the design of centralized communication networks. In this paper we consider the multi-level capacitated minimum spanning tree problem, a generalization of the well-known CMST problem. Based on work previously done in the field, three heuristics are presented, addressing unit and non-unit demand cases. The proposed heuristics have been also integrated into a mixed integer programming solver. Evaluation results are presented, for an extensive set of experiments, indicating the improvements that the heuristics bring to the particular problem. 相似文献
19.
We consider the generalized version of the classical Minimum Spanning Tree problem where the nodes of a graph are partitioned
into clusters and exactly one node from each cluster must be connected. We present a Variable Neighborhood Search (VNS) approach
which uses three different neighborhood types. Two of them work in complementary ways in order to maximize search effectivity.
Both are large in the sense that they contain exponentially many candidate solutions, but efficient polynomial-time algorithms
are used to identify best neighbors. For the third neighborhood type we apply Mixed Integer Programming to optimize local
parts within candidate solution trees. Tests on Euclidean and random instances with up to 1280 nodes indicate especially on
instances with many nodes per cluster significant advantages over previously published metaheuristic approaches.
This work is supported by the RTN ADONET under grant 504438. 相似文献
20.
The diameter-constrained minimum spanning tree problem is an NP-hard combinatorial optimization problem that seeks a minimum cost spanning tree with a limit D imposed upon the length of any path in the tree. We begin by presenting four constructive greedy heuristics and, secondly,
we present some second-order heuristics, performing some improvements on feasible solutions, hopefully leading to better objective
function values. We present a heuristic with an edge exchange mechanism, another that transforms a feasible spanning tree
solution into a feasible diameter-constrained spanning tree solution, and finally another with a repetitive mechanism. Computational
results show that repetitive heuristics can improve considerably over the results of the greedy constructive heuristics, but
using a huge amount of computation time. To obtain computational results, we use instances of the problem corresponding to
complete graphs with a number of nodes between 20 and 60 and with the value of D varying between 4 and 9. 相似文献