LOCAL SEARCH WITH PERTURBATIONS FOR THE PRIZE-COLLECTING STEINER TREE PROBLEM IN GRAPHS
S.A.CANUTO,M.G.C.RESENDE,AND C.C.RIBEIRO
Abstract.Given an undirected graph with prizes associated with its nodes
and weights associated with its edges,the prize-collecting Steiner tree problem
consists in?nding 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 multi-start 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 https://www.doczj.com/doc/f59978271.html,putational experiments involving di?erent
algorithm variants are reported.Our results show that the local search with
perturbations approach found optimal solutions on nearly all of the instances
tested.
Let G=(V,E)be a connected undirected graph,where V is the set of nodes and E denotes the set of edges,together with a nonnegative weight function w:E→+ associated with its edges and a nonnegative prize functionπ:V→+associated with its nodes.In the prize-collecting Steiner tree problem(PCSTP),one wants to ?nd a subtree of G=(V,E)which minimizes the sum of the weights of its edges plus the prizes of the nodes not spanned.
The prize collecting Steiner tree problem has an important application in telecom-munication local access network design,so as to balance the potential revenue that can be obtained by providing service to customers and the cost to build the network. In this application,a?ber-optic network that provides local service to customers is to be built.In the associated graph,edges are street segments where?ber can be laid.Edge weights are the costs associated with laying the?ber cable along street segments.Nodes in the graph are street intersections and the locations of customer premises,which one can assume are on or near the streets.Node prizes are estimates of the potential revenue to be obtained by providing service to the customers on that node.
We notice that if the subset of nodes X to be spanned is known,we have the Steiner tree problem,which consists in?nding a minimum weighted connected sub-tree of G spanning all nodes in X.The Steiner problem in graphs is a classical combinatorial optimization problem,whose decision version has been shown to be NP-complete by Karp(1972).Since the Steiner problem in graphs is a particular case of the PCSTP in which all terminal nodes have in?nite prizes and the others have null prizes,then the decision version of PCSTP is also NP-complete.
2S.A.CANUTO,M.G.C.RESENDE,AND C.C.
RIBEIRO
Construction heuristics and lower bounds based on Lagrangian relaxation for the PCSTP have been proposed by Segev(1987)and Engevall,G¨o the-Lundgren, and V¨a rbrand(1998).Both papers report limited computational experience for small graphs having5to100nodes.More recently,Johnson,Minko?,and Phillips (2000)described an implementation of the primal-dual2-approximation algorithm of Goemans and Williamson(1996),for which extensive computational results on large instances are reported.
In this paper,we propose a local search approach with perturbations for?nd-ing approximate solutions to the prize-collecting Steiner tree problem and report computational results for large graphs with up1000nodes and25,000edges.The approach is based on a neighborhood de?ned by the set of nodes spanned by the current solution.In the next section,we de?ne the neighborhood structure and the basic iterative improvement algorithm used for local search.The multi-start perturbation algorithm is described in Section2.In Section3we describe a path-relinking scheme for search intensi?cation and solution improvement.The full al-gorithm,combining the previous local search with perturbations algorithm and path-relinking with a variable neighborhood search procedure is described in https://www.doczj.com/doc/f59978271.html,putational results are reported in Section5.Concluding remarks are drawn in the last section.
1.Local search and neighborhood structure
Given the graph G=(V,E)together with cost functions w(·)andπ(·),we associate a solution T(X)of the prize-collecting Steiner tree problem to each subset X?V of nodes,de?ned by a minimum spanning tree of the graph induced in G by X.The characteristic vector associated with the solution de?ned by the subset X of nodes is v X∈{0,1}|V|,such that v X(i)=1if i∈X;v X(i)=0otherwise.We de?ne T p(X)to be the tree obtained from T(X)by recursively eliminating from T(X)all degree-1nodes whose incident arc has weight greater than its prize.The cost c(X)of solution T(X)is given by the sum of the weights of all edges in T p(X) plus the sum of the prizes of all nodes not spanned by T p(X).
We illustrate in Figures1–3the peeling procedure leading from tree T(X)to T p(X).In each?gure,nodes in black are those spanned by the current solution using the edges drawn in black.Dashed edges and empty(white)nodes are not part of the solution.Numbers on the edges are edge weights,while number in the nodes are node prizes.Figure1represents the current solution T(X)whose sum
LOCAL SEARCH FOR THE PRIZE COLLECTING STEINER TREE PROBLEM
3 Figure2.Solution after?rst peeling
iteration.
Figure3.Solution T p(X)after peeling.
of edge weights and non-spanned node prizes is15.Since the leaf with node prize two is connected by an incident edge with weight three,it can be removed leading to the tree in Figure2.Once again,the node with prize equal to four in this?gure is connected by an edge with larger weight(?ve)and can then be also removed. The solution T p(X)obtained by the peeling procedure has cost c(X)=13and is illustrated in Figure3.
The neighborhood N(1)(X)of a solution T(X)is formed by all minimum span-ning trees T(X′)whose sets X′of nodes di?er from X by exactly one node,i.e.,
i=|V|
i=1|v X′(i)?v X(i)|=1.
A local search approach based on neighborhood structure N(1)starts from some solution T(X)associated with a set X of terminal nodes and progressively replaces it by the?rst improving move it?nds within neighborhood N(1)(X).The algorith-mic description of this basic iterative improvement approach used for local search is given in Figure4.The loop from line2to15is performed until no further improvement is possible.Lines3to7control the neighborhood search,which in-vestigates all possible insertions and eliminations of nodes.To speedup the search, the neighborhood investigation starts from the node following that which led to the improving move obtained in the previous iteration(circularity).The cost c(X′)of neighbor T(X′)has two components and is computed in line8.The?rst component is the cost of the minimum spanning tree of the graph induced in G by the nodes of T p(X′),using Kruskal’s algorithm(Kruskal1956),to which we add the prizes of the nodes not spanned by this tree.Whenever an improving neighbor is found,it replaces the current solution and local search resumes from this new solution(lines
4S.A.CANUTO,M.G.C.RESENDE,AND C.C.RIBEIRO
9to13).Local search stops when all neighbors have been evaluated and no further reduction in terms of solution cost is possible.
procedure It
improvement←.TRUE.;
2while local
improvement←.FALSE.;
4circfor i=1,...,|V|while.NOT.local
improvement←.TRUE.;
13end
circfor;
15end
Impr;
Figure4.Pseudo code of the iterative improvement algorithm
for local search.
2.Perturbation algorithm
The perturbation algorithm described in this section is a multi-start approach, with initial solutions provided by the primal-dual algorithm GW of Goemans and Williamson(1996).The algorithm is also similar to a GRASP procedure(Feo and Resende1995),in which the greedy randomized construction is replaced by the construction of initial solutions using perturbed cost functions.
The basic structure of the local search with perturbation algorithm is presented in Figure5.At each iteration,a new initial solution is constructed by the primal-dual algorithm GW.The original node prizesπare used in the?rst iteration,but they are modi?ed along the forthcoming iterations to enforce diversi?cation of the solutions computed by algorithm GW.The spanning tree T(X)associated with the subset X of nodes spanned by the solution constructed in this way is submitted to the local search algorithm It
LOCAL SEARCH FOR THE PRIZE COLLECTING STEINER TREE PROBLEM5 procedure LS
value←+∞;
2
iterations do
4X←GW(V,E,w,
Impr(V,E,w,π,X);
6if c(ˉX) value←c(ˉX); 10end π; 12end Perturbations; Figure5.Pseudo code of the basic local search with perturba- tions algorithm. a parameterαand we change to zero the prizes associated with a randomly chosen set containingα%of the persistent nodes observed in the previous iteration.?Perturbation by prize changes:Another strategy to force GW to build di?erent,but still good solutions,consists in introducing some noise into node prizes,similarly to what is proposed by Charon and Hudry(1993),so as to change the objective function.For each node i∈V,a perturbation factorβis randomly generated in the interval[1?a,1+a],where a is an implementation parameter,and the prize associated with node i is changed to pool high-quality diverse elite solutions is stored to serve as guiding solutions for path-relinking. Each iteration of algorithm LS 6S.A.CANUTO,M.G.C.RESENDE,AND C.C.RIBEIRO the best(most decreasing or least increasing)remaining move still in this list until ˉY is attained.The best solution?X found along this trajectory replaces the worst solution currently in the pool if it satis?es either one of the following criteria:?c(?X)is less than the cost of the best solution currently in the pool; ?c(?X)is less than the cost of the worst solution currently in the pool and?X is su?ciently di?erent from all solutions in the pool.For two solutions to be considered as su?ciently di?erent,the Hamming distance between their characteristic vectors must be greater than a speci?ed nonnegative threshold parameterρ≤1multiplied by the number of vertices in the graph. 4.Full algorithm with post-optimization In this section,we describe a full algorithm for the PCSTP combining the pre-vious local search with perturbations algorithm and path-relinking with a variable neighborhood search used as a post-optimization step. The variable neighborhood search(VNS)metaheuristic,proposed by Mladen-ovi′c and Hansen(1997),is based on the exploration of a dynamic neighborhood model.We use VNS as a post-processing optimization procedure applied to the best solution found by the local search with perturbations algorithm described in Section2. The k-th order neighborhood N(k)(X)of a solution T(X)is formed by all mini-mum spanning trees T(X′)whose sets X′of nodes di?er from X by exactly k nodes, i.e., i=|V| i=1|v X′(i)?v X(i)|=k.Let k max be the order of the highest neighborhood explored. procedure VNS(V,E,w,π,X) 1for t=1,...,max Impr(V,E,w,π,?X); 6if c(ˉX) 7then do 8X←ˉX; 9k←1; 10end while 13end trials iterations in which the sequence of neighborhoods N(1)(X),...,N k max(X)is explored without ?nding any improving solution.Each trial starts in line2using the?rst order LOCAL SEARCH FOR THE PRIZE COLLECTING STEINER TREE PROBLEM7 neighborhood.The loop from lines3to12explores a sequence of increasing order neighborhoods.A subset?X of nodes belonging to the k-th order neighborhood leading to a feasible solution T(?X)is randomly generated in line4.The It PCSTP described in Figure7incorporates the path-relinking strategy and the VNS post-optimization procedure to algorithm LS Impr procedure given in Section1starting from X.Solution?X is inserted in the pool of elite solutions in line8if either one of the membership conditions described in Section3((i)optimality with respect to the solutions currently in the pool,or(ii)quality and diversity)is satis?ed.Next,a solutionˉY is randomly selected from the pool of elite solutions in line9.The path-relinking scheme de-scribed in Section3is applied toˉX usingˉY as the guiding solution,leading to the best solution?X in the trajectory(line10).The incumbent solution and its value are recorded in lines11to15.Once again,in line16we check for the insertion of solution?X in the pool of elite solutions if either one of the membership conditions is satis?ed.In line18,the node prizesˉπare updated for the next iteration,according to a perturbation scheme.Finally,the VNS procedure is applied in line20to the incumbent solution. https://www.doczj.com/doc/f59978271.html,putational Results Since few benchmark instances for the prize-collecting Steiner tree problem are available,we have generated a set of80test problems derived from the Steiner problem instances of the OR-Library(Beasley1990).For each of the40problems from series C and D,we generated two sets of test instances.All original non terminal nodes receive a null prize.A prize randomly generated in the interval [1,max prize=10 for problems in set A and max PCSTP described in Section4and all other procedures have been coded in C and compiled with gcc version2.7.2.3under Linux version2.0.36.All computational experiments were performed on a400MHz IBM Pentium II com-puter with64Mbytes of memory. 8S.A.CANUTO,M.G.C.RESENDE,AND C.C.RIBEIRO procedure LS value←∞; 2ˉπ←π; 3for i=1,...,max Impr(V,E,w,π,X); 8InsertˉX in the pool if membership conditions are satis?ed; 9Randomly select a solutionˉY from the pool of elite solutions; 10Let?X be the best solution found by path-relinkingˉX andˉY; 11if c(?X) value←c(?X); 15end then; 18Compute perturbations and updateˉπ; 19end PCSTP; Figure7.Pseudo code of the full algorithm for PCSTP. The perturbation scheme used in algorithm LS iterations=500,max pool=10. The random number generator of Schrage(1979)is used.We use an early version of the C implementation of the Goemans and Williamson algorithm developed by Johnson,Minko?,and Phillips and described in(Johnson,Minko?,and Phillips 2000). We present in Tables1and2the computational results for the test problems derived from the instances in the OR-Library.For each instance,this table shows its identi?cation,its number of nodes and edges,the value of the initial solution obtained with the Goemans and Williamson algorithm,the value of the solution obtained with the original prizes after the?rst iteration of algorithm LS PCSTP without VNS(together with the corresponding computation time in seconds for the500iterations),the value of the solution obtained with the full algorithm LS LOCAL SEARCH FOR THE PRIZE COLLECTING STEINER TREE PROBLEM9 whether this bound is tight.We present the same statistics for the test problems of (Johnson,Minko?,and Phillips2000)in Table3.On all of these tables,we indicate with bold face whenever a provably optimal solution is found. Table1.Run statistics on test instances derived from series C OR-Library problems Problem GW It.Impr.LS+PR Time VNS Time C.01-A1818183 50062585y C.02-A5050507 500625141y C.03-A41441441487 500625737y C.04-A626626618148 5006251063y C.05-A109010861080447 5006251528y C.06-A1818189 500100055y C.07-A50505034 5001000102y C.08-A376368361313 5001000500y C.09-A541537533475 5001000694y C.10-A870860859628 50010001069y C.11-A181818128 500250032y C.12-A403938162 500250046y C.13-A247238237797237253 5002500258y C.14-A309295293829 5002500318y C.15-A515503501957 5002500551y C.16-A151212429111491 5001250011y C.17-A202018549 5001250018y C.18-A1301161113990 50012500113y C.19-A1651491463928 50012500146y C.20-A27126626630092661302 50012500264? We next make some observations concerning the computational results.We refer to the instances derived from the Series C and D test problems of the OR-Library as Series C and Series D,respectively.The instances from(Johnson,Minko?,and Phillips2000)are referred to as Series JMP. Table4summarizes for each algorithm variant and for each series,the number of test instances,the number of optimal solutions found,the number of solutions within1%,5%,and10%of the linear programming lower bound,and the largest 10S.A.CANUTO,M.G.C.RESENDE,AND C.C.RIBEIRO Table2.Run statistics on test instances derived from series D OR-Library problems Problem GW It.Impr.LS+PR Time VNS Time D.01-A1818186 10001250106y D.02-A5050507 10001250218y D.03-A815809807734 100012501509y D.04-A1211120512031263 100012501881y D.05-A21952171215829102157442 100012503135y D.06-A18181820 1000200067y D.07-A505050195 10002000103y D.08-A7687607551727 100020001036y D.09-A11151085107236271072482 100020001420y D.10-A1735168416714193 100020002079y D.11-A181818540 1000500029y D.12-A444242844 1000500042y D.13-A4824534455047 10005000486y D.14-A6486076026388 10005000664? D.15-A108310451042636610421474 100050001105? D.16-A1717131397 10002500013y D.17-A2523233506 10002500023y D.18-A26123721830044 100025000223? D.19-A353318308340383086917 100025000310? D.20-A550537536213295366810 100025000530? percentage deviation from this lower bound.We compute percentage deviation of the solution value z from the lower bound l z as100·(z?l z)/l z.We?rst notice that the behavior of the implementation of the Goemans and Williamson 2-approximation algorithm used in our study was much better than its worst case guaranteed performance.With this version of GW,the worst-quality solution found was38.5%from the optimal value.Recently,Johnson,Minko?,and Phillips(2000) further developed their implementation,resulting in slight improvements with re-spect to the version we used in this study.For example,with their new imple-mentation,the deviation from the optimal value of the worst-quality solution was LOCAL SEARCH FOR THE PRIZE COLLECTING STEINER TREE PROBLEM11 Table3.Run statistics on test instances from Johnson,Minko?, and Phillips(2000). Problem GW It.Impr.LS+PR Time VNS Time P10081328280915080330015 100284926238y P100.24192554016414016415 100316659644y P100.482778982741982741910 2005871317874y P400256742924799962459904397 40012122808440y P400.2258400925699642518577396 40011752951725y P400.43003004288175728529564262852956139 100351135511y K100.11241081241081241082 100339200262y K100.31159531159531159533 10036487498y K100.51190781190781190782 100307132886y K100.71724571724571724572 100343210869y K100.91229171229171229172 100319133567y K2003328733328733292119 4001515350093y K400.149443449242449116087490771107 4001527477073y K400.34174214153284153287641532864 4001426389451y K400.5534287529581519526122 4001576374849y K400.7491539486533478220194475130112 4001516418614y K400.939402638714238310576 4001507394191y reduced from38.5%to18.18%.From the?rst part of Table4we observe that the instances from Series JMP are the easiest for algorithm GW,while those of Series D are the hardest.Running times for GW are negligible on these instances.The remainder of Table4illustrates the e?ect of adding the following additional com-ponents to the full LS 12S.A.CANUTO,M.G.C.RESENDE,AND C.C.RIBEIRO Table4.Performance of GW and successive variants of local search. Algorithm Optimal≤1%≤5%≤10% 8153234 C4036.4% 572131 14243434 C4011.1% 11223337 26323434 C409.1% 22343839 29323434 C40 1.1% 25344040 PCSTP algorithm.For each series,we?rst give the number of instances not solved to optimality by GW.For each additional component of the full LS PCSTP without VNS was about0.7%.However,the LOCAL SEARCH FOR THE PRIZE COLLECTING STEINER TREE PROBLEM 13 5 10 15 20 25 30 35 40 5 10 15 20 25 30 35 40 c u m m u l a t i v e n u m b e r o f i n s t a n c e s deviation from the optimal value (%) GW It. Impr.LS+PR VNS Figure 9.Performance of GW and successive variants of local search for Series C problems. Table 5.Improvement of successive variants of local search over GW . It.Impr.VNS #Opt %impr #Opt %impr Time 6 1.2 21 2.5 94.1 C 34 27 8.6 956.8 6 4.7 20 7.5 2749.2 average running times for VNS alone are almost of the same magnitude as those of LS PCSTP algorithm was in general much faster. For example,instances K400.1to K400.10from series JMP required about one day of CPU on a Silicon Graphics Challenge computer,while the full LS PCSTP algorithm was able to ?nd optimal solutions for all small size problems having 100nodes within a few seconds of computation time.These problems are comparable with the largest ones considered by Engevall,G¨o the-Lundgren,and V¨a rbrand (1998),for which their algorithms did not ?nd optimal solutions in about 9%of the cases.Segev (1987)reported computational experience only for smaller graphs having 5to 40nodes. 14 S.A.CANUTO,M.G.C.RESENDE,AND C.C.RIBEIRO 5 10 15 20 25 30 35 40 5 10 15 20 25 30 35 40 c u m m u l a t i v e n u m b e r o f i n s t a n c e s deviation from the optimal value (%) GW It. Impr.LS+PR VNS Figure 10.Performance of GW and successive variants of local search for Series D problems. 6.Concluding Remarks In this paper,we have investigated local search strategies for the prize-collecting Steiner tree problem:iterative improvement,multi-start with perturbations,path-relinking,and variable neighborhood search.All strategies have been shown to be e?ective in improving solutions constructed by the primal-dual 2-approximation algorithm of Goemans and Williamson.Optimal solutions have been found for most test instances.In particular,we stress the e?ectiveness of path-relinking as an intensi?cation strategy in metaheuristic implementations. References J.E.Beasley.OR-Library:Distributing test problems by electronic mail.Journal of the Operational Research Society ,41:1069–1072,1990. I.Charon and O.Hudry.The noising method:A new method for combinatorial optimization.Operations Research Letters ,14:133–137,1993.S.Engevall,M.G¨o the-Lundgren,and P.V¨a rbrand.A strong lower bound for the node weighted Steiner tree https://www.doczj.com/doc/f59978271.html,works ,31:11–17,1998. T.A.Feo and M.G.C.Resende.Greedy randomized adaptive search procedures.Journal of Global Optimization ,6:109–133,1995. F.Glover.Tabu search and adaptive memory programming –Advances,applica-tions and challenges.Technical report,University of Colorado,1996. F.Glover and https://www.doczj.com/doc/f59978271.html,guna.Tabu Search .Kluwer Academic Publishers,1997. M.X.Goemans and D.P.Williamson.The primal dual method for approximation algorithms and its application to network design problems.In D.Hochbaum, LOCAL SEARCH FOR THE PRIZE COLLECTING STEINER TREE PROBLEM15 editor,Approximation algorithms for NP-hard problems,pages144–191.PWS Publishing Co.,1996. D.S.Johnson,M.Minko?,and S.Phillips.The prize collecting Steiner tree prob-lem:Theory and practice.In Proc.11th ACM-SIAM Symp.on Discrete Algo-rithms,pages760–769,2000. R.M.Karp.Reducibility among combinatorial problems.In https://www.doczj.com/doc/f59978271.html,ler and J.W. Thatcher,editors,Complexity of Computer Computations,pages85–103.Plenum Press,1972. J.B.Kruskal.On the shortest spanning tree of a graph and the traveling salesman problem.In Proceedings of the American Mathematical Society,volume7,pages 48–50,1956. https://www.doczj.com/doc/f59978271.html,guna and R.Mart′?.GRASP and path relinking for2-layer straight line crossing https://www.doczj.com/doc/f59978271.html,RMS J.on Computing,11:44–52,1999. A.Lucena and M.G.C.Resende.Strong lower bounds for the prize collecting Steiner tree problem.Technical report,AT&T Labs Research,1999. N.Mladenovi′c and P.Hansen.Variable neighbourhood https://www.doczj.com/doc/f59978271.html,puters and Operations Research,24:1097–1100,1997. L.Schrage.A more portable Fortran random number generator.ACM Transactions on Mathematical Software,5:132–138,1979. A.Segev.The node-weighted Steiner tree https://www.doczj.com/doc/f59978271.html,works,17:1–17,1987. (S.A.Canuto)Department of Computer Science,Catholic University of Rio de Janeiro, r.Marqu?e s de S?a o Vicente,225,Rio de Janeiro,RJ22453-900Brazil E-mail address,S.A.Canuto:suzana@inf.puc-rio.br (M.G.C.Resende)Information Sciences Research,AT&T Labs Research,Florham Park,NJ07932USA. E-mail address,M.G.C.Resende:mgcr@https://www.doczj.com/doc/f59978271.html, (C.C.Ribeiro)Department of Computer Science,Catholic University of Rio de Janeiro, r.Marqu?e s de S?a o Vicente,225,Rio de Janeiro,RJ22453-900Brazil E-mail address,C.C.Ribeiro:celso@inf.puc-rio.br
相关主题
文本预览