×

zbMATH — the first resource for mathematics

A comparison of problem decomposition techniques for the FAP. (English) Zbl 1187.90181
Summary: This paper proposes a problem decomposition approach to solve hard Frequency Assignment Problem instances with standard meta-heuristics. The proposed technique aims to divide the initial problem into a number of easier subproblems, solve them and then recompose the partial solutions into one of the original problem. We consider the COST-259 MI-FAP instances and other Cardiff University test problems in order to simulate larger and more realistic networks. For both benchmarks the standard implementations of meta-heuristics do not generally produce a satisfactory performance within reasonable times of execution. However, the decomposed assignment approach can improve their results, both in terms of solution quality and runtime.
MSC:
90B85 Continuous location
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
Software:
FASoft
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aardal, K.I., van Hoesel, C.P.M., Jansen, B.: A branch-and-cut algorithm for the frequency assignment problem, R.M. 96\(\backslash\)11 (1996)
[2] Abbiw-Jackson, R., Golden, B., Raghavan, S., Wasil, E.: A divide-and-conquer local search heuristic for data visualization. Comput. Oper. Res. 33(11), 3070–3087 (2006) · Zbl 1113.90127 · doi:10.1016/j.cor.2005.01.020
[3] Allen, S.M., Dunkin, N., Hurley, S., Smith, D.: Frequency assignment problems: benchmarks and lower bounds. University of Glamorgan (1998)
[4] Angelsmark, O., Thapper, J.: Partitioning Based Algorithms for Some Colouring Problems. Lecture Notes in Computer Science, vol. 3978, pp. 44–58 (2006) · Zbl 1180.68242
[5] Beckmann, D., Killat, U.: Frequency planning with respect to interference minimization in cellular radio networks. Tech. Rep. 8th COST 259 Meeting, Vienna, Austria (1999)
[6] Borovska, P.: Solving the travelling salesman problem in parallel by genetic algorithm on multicomputer cluster. In: Proc. of the International Conference on Computer Systems and Technologies CompSysTech’06, Veliko Tarnovo, Bulgaria, 2006
[7] Brandes, U., Gaertler, M., Wagner, D.: Experiments on graph clustering algorithms. In: Proc. of the 11th Annual European Symposium on Algorithms, Budapest, 2003 · Zbl 1143.05311
[8] Cardiff University Condor Pool. http://www.cardiff.ac.uk/insrv/it/condor/index.html , accessed on 1st June 2007
[9] Cheng, C.B., Wang, K.P.: Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm. Expert Syst. Appl. 36(4), 7758–7763 (2009) · Zbl 05856848 · doi:10.1016/j.eswa.2008.09.001
[10] Colombo, G.: A genetic algorithm for frequency assignment with problem decomposition. Int. J. Mob. Netw. Des. Innov. 1(2), 102–112 (2006) · doi:10.1504/IJMNDI.2006.010812
[11] Colombo, G., Allen, S.M.: Problem decomposition for minimum interference frequency assignment. In: Proc. of the 2007 IEEE Congress in Evolutionary Computation, Singapore, 2007
[12] Colombo, G.: A decomposition approach for the frequency assignment problem. Ph.D. Thesis, Cardiff University, UK (2008) · Zbl 1147.90371
[13] Correia, L.M. (ed.): Wireless Flexible Personalised Communications. Wiley, Chichester (2001)
[14] Crainic, T.G., Toulouse, M.: Parallel Strategies for Meta-heuristic. State-of-the-Art Handbook in Metaheuristics, edited by Glover, F., Kochenberger, G., Kluwer Academic, Dordrecht (2002)
[15] Crompton, W., Hurley, W.S., Stephens, N.M.: A parallel genetic algorithm for frequency assignment problems. In: Proc. of the IMAC-IEEE Conference on Signal Processing, Robotics and Neural Networks, Lille, France, 1994
[16] Eisenblatter, A.: Frequency assignment in GSM networks: Models, heuristics, and lower bounds. Ph.D. Thesis, Technische Universitat Berlin, Berlin, Germany (2001)
[17] FAP web–A website about Frequency Assignment Problems. http://fap.zib.de/ , accessed on 1st June 2007
[18] Gendreau, M., Guertin, F., Potvin, J.Y., Taillard, E.: Parallel tabu search for real-time vehicle routing and dispatching. Transp. Sci. 33(4), 381–390 (1999) · Zbl 0958.90051 · doi:10.1287/trsc.33.4.381
[19] Gonzales Hernandez, L.F., Corne, D.W.: Evolutionary divide and conquer for the set-covering problem. In: Lecture Notes in Computer Science, vol. 1143, pp. 198–208 (1996)
[20] Hale, W.K.: Frequency assignment: Theory and applications. Proc. IEEE 68(12), 1497–1514 (1980) · doi:10.1109/PROC.1980.11899
[21] Hellebrandt, M., Heller, H.: A new heuristic method for frequency assignment. Tech. Report TD(00) 003, COST259, Valencia, Spain (Jan. 2000)
[22] Hurley, S., Smith, D.: Meta-heuristics and channel assignment. In: Hurley, S., Leese, R. (eds.) Methods and Algorithms for Radio Channel Assignment. Oxford University Press, Oxford (2002) · Zbl 1027.94500
[23] Hurley, S., Smith, D., Thiel, S.U.: FASoft: A system for discrete channel frequency assignment. Radio Sci. 32(5), 1921–1939 (1997) · doi:10.1029/97RS01866
[24] Gendron, B., Crainic, T.G.: Parallel branch-and-bound algorithms: Survey and synthesis. Oper. Res. 42(6), 1042–1066 (1994) · Zbl 0824.90096 · doi:10.1287/opre.42.6.1042
[25] Karaoglu, N., Manderick, B.: FAPSTER–a genetic algorithm for frequency assignment problem. In: Proc. of the 2005 Genetic and Evolutionary Computation Conference, Washington D.C., USA, 2005
[26] Karp, R.M.: Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Math. Oper. Res. 2(3), 209–224 (1977) · Zbl 0391.90091 · doi:10.1287/moor.2.3.209
[27] Koster, A.M.C.A., van Hoesel, C.P.M., Kolen, A.W.J.: Solving partial constraint satisfaction problems with tree decomposition. Networks 40(3), 170–180 (2002) · Zbl 1027.90072 · doi:10.1002/net.10046
[28] Kravets, V.L., Sergienko, I.V.: Decomposition method of solving a class of combinatorial optimization problems. Cybern. Syst. Anal. 19(6), 833–837 (1983) · Zbl 0559.90059 · doi:10.1007/BF01068574
[29] Mannino, C., Sassano, A.: An enumerative algorithm for the frequency assignment problem. Discrete Appl. Math. 129(1), 155–169 (2003) · Zbl 1023.68004 · doi:10.1016/S0166-218X(02)00239-1
[30] Mannino, C., Oriolo, G., Ricci, F.: Solving stability problems on a superclass of interval graphs. T.R. n. 511, Vito Volterra (2002)
[31] Montemanni, R., Moon, J.N., Smith, D.H.: An improved tabu search algorithm for the fixed-spectrum frequency-assignment problem. IEE Trans. Veh. Technol. 52(3), 891–901 (2003) · doi:10.1109/TVT.2003.810976
[32] Pardalos, P., Rappe, J., Resende, M.: An exact parallel algorithm for the maximum clique problem. In: De Leone, P.P.R., Murl’i, A., Toraldo, G. (eds.) High Performance Algorithms and Software in Nonlinear Optimization. Kluwer, Dordrecht (1998) · Zbl 0944.90111
[33] Pekny, J.F., Miller, D.L.: An exact parallel algorithm for the resource constrained traveling salesman problem with application to scheduling with an aggregate deadline. In: Proc. of the 1990 ACM Annual Conference on Cooperation, Washington, D.C., USA, 1990
[34] Ralphs, T.K.: Parallel branch and cut for capacitated vehicle routing. Parallel Comput. 29(5), 607–629 (2003) · doi:10.1016/S0167-8191(03)00045-0
[35] Schabauer, H., Schikuta, E., Weishaupl, T.: Solving very large traveling salesman problems by SOM parallelization on cluster architectures. In: Proc. of Sixth International Conference on the Parallel and Distributed Computing, Applications and Technologies, Vienna, Austria, 2005
[36] Taillard, E.D.: Parallel iterative search methods for vehicle routing problems. Networks 23, 661–673 (1993) · Zbl 0804.90045 · doi:10.1002/net.3230230804
[37] Taillard, E.D.: Parallel taboo search techniques for the job shop scheduling problem. ORSA J. Comput. 6(2), 108–117 (1994) · Zbl 0807.90066
[38] Talbi, E.G., Mostaghim, S., Okabe, T., Ishibuchi, H., Rudolph, G., Coello, C.A.: Parallel approaches for multiobjective optimization. In: Lecture Notes in Computer Science, vol. 5252, pp. 349–372 (2008)
[39] Toulouse, M., Thulasiraman, K., Glover, F.: Multi-level cooperative search: a new paradigm for combinatorial optimization and an application to graph partitioning. In: Lecture Notes in Computer Science, vol. 1685, pp. 533–542 (1999)
[40] Valenzuela, C.L., Jones, A.J.: Evolutionary divide and conquer (I): A novel genetic approach to the TSP. Evol. Comput. 1(4), 313–333 (1993) · Zbl 05412906 · doi:10.1162/evco.1993.1.4.313
[41] van Dongen, S.: A cluster algorithm for graphs. Technical Report INS-R0010, National Research Institute for Mathematics and Computer Science in the Netherlands, Amsterdam (2000)
[42] Walshaw, C.: A multilevel approach to the graph colouring problem. Tech. Rep. 01/IM/69, University of Greenwich, London (2001) · Zbl 1043.68637
[43] Zhang, Y.: Parallel algorithms for combinatorial search problems. Ph.D. Thesis, University of California at Berkeley (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.