Document Type : Research Article
Authors
1 Faculty of Mathematical Sciences, Department of Applied Mathematics, Ferdowsi University of Mashhad, Mashhad, Iran.
2 Mosaheb Institute of Mathematics, Kharazmi University, Tehran, Iran.
10.30473/coam.2025.74009.1296
Abstract
In this study, we proposed a novel graph partitioning problem where the edges are characterized by trapezoidal fuzzy numbers. A linear ranking function is employed to establish an order among these fuzzy numbers. We derive the necessary conditions for the existence of an optimal solution to this problem. To address the fuzzy graph partitioning problem, we implement and compare the performance of three algorithms: Genetic Algorithm, Tabu Search, and Sequential Least Squares Programming. The algorithms are evaluated based on objective values, computational time, and the number of iterations across multiple numerical examples. Utilizing Dolan-Moré performance profiles, we demonstrate the superiority of our proposed approach relative to existing methods. The findings highlight the robustness and computational efficiency of our methodology, making a meaningful contribution to the advancement of fuzzy graph algorithms and their practical applications.
Highlights
- Formulated a novel graph partitioning problem where the edges are represented by trapezoidal fuzzy numbers.
- Applied a linear ranking function to systematically and effectively order the trapezoidal fuzzy numbers, facilitating decision-making and optimization.
- Established necessary conditions that must be satisfied for the existence of an optimal solution to the fuzzy GPP, providing theoretical insights into the problem's solvability.
- Implemented and compared three distinct optimization techniques, Genetic Algorithm, Tabu Search, and Sequential Least Squares Programming, to solve the fuzzy GPP efficiently.
- Conducted extensive numerical testing to evaluate each approach based on objective function value, computational time, and iteration number across multiple instances.
- Employed Dolan-Moré performance profiles to visually demonstrate the efficiency and robustness, and reliability of the proposed approach.
Keywords
Main Subjects
[1] Abouyee Mehrizi, A., Ghanbari, R., Sadeghi, S., Ghorbani-Moghadam, Kh. (2024). “Solving continuous quadratic programming for the discrete balanced graph partitioning problem using simulated annealing algorithm, hybridized local search and multi-start algorithms”, Applied Soft Computing Journal, 165, 112109, doi: https://doi.org/10.1016/ j.asoc.2024.112109.
[2] Bäck, T. (1996). “Evolutionary algorithms in theory and practice: Evolution strategies, evolutionary programming, genetic algorithms”, New York, 1996; Online Edn, Oxford Academic, doi: https://doi.org/10.1093/ oso/9780195099713.001.0001.
[3] Baeck, T., Fogel, D.B, Michalewicz, Z. (1997). “Handbook of evolutionary computation” (1st ed.). CRC Press. doi: https://doi.org/10.1201/9780367802486.
[4] Benlic, U., Hao, J.K. (2011). “An effective multilevel tabu search approach for balanced graph partitioning”, Computers & Operations Research, 38(7), 1066-1075, doi: https://doi.org/10.1016/j.cor.2010.10.007.
[5] Boulif, M. (2010). “Genetic algorithm encoding representations for graph partitioning problems”, International Conference on Machine and Web Intelligence, Algiers, Algeria, 2010, 288-291, doi: https://doi.org/10.1109/ICMWI.2010.5648133.
[6] Bruglieri, M., Cordone, R. (2021). “Metaheuristics for the minimum gap graph partitioning problem”, Computers & Operations Research, 132, 105301, doi: https://doi.org/10.1016/j.cor.2021.105301.
[7] Brunetta, L., Conforti, M., Rinaldi, G. (1997). “A branch-and-cut algorithm for the equicut problem”, Mathematical Programming, 78, 243-263, doi: https://doi.org/10.1007/BF02614373.
[8] Bui, T.N., Moon, B.R. (1996). “Genetic algorithm and graph partitioning”, IEEE Transactions on Computers, 45(7), 841-855, doi: https://doi.org/10.1109/12.508322.
[9] Chaouche, A., Boulif, M. (2019). “Solving the unsupervised graph partitioning problem with genetic algorithms: Classical and new encoding representations”, Computers & Industrial Engineering, 137, 106025, doi: https://doi.org/10.1016/j.cie.2019.106025.
[10] Delgado, M., Verdegay, H.K., Vila, A.A. (1990). “On valuation and optimization problems in fuzzy graphs: A general approach and some particular cases”, ORSA Journal on Computing, 2(1), 74-83, doi: https://doi.org/10.1287 /ijoc.2.1.74.
[11] Dolan, E., Moré, J. (2002). “Benchmarking optimization software with performance profiles”, Mathematical Programming, 91, 201-213, doi: https://doi.org/10.1007/s101070100263.
[12] Eiben, A.E., Smith, J.E. (2015). “Introduction to evolutionary computing”, Springer, doi: https://doi.org/10. 1007/978-3-662-44874-8.
[13] Farshbaf, M., Feizi-Derakhshi, M.R. (2009). “Multi-objective optimization of graph partitioning using genetic algorithms.”, Third International Conference on Advanced Engineering Computing and Applications in Sciences, Sliema, Malta, 1-6, doi: https://doi.org/10.1109/ADVCOMP.2009.8.
[14] Firouzian, S., Adabitabar Firozja, M. (2016). “Fuzzy number-valued fuzzy graph”, Control and Optimization in Applied Mathematics, 1(2), 77-86.
[15] Firouzian, S., Sedghi, S., Shobe, N. (2021). “On edge fuzzy line graphs and their fuzzy congraphs”, Control and Optimization in Applied Mathematics, 6(1), 81-89, doi: https://doi.org/10.30473/coam.2021.44084.1102.
[16] Gill, P.E., Murray, W., Wright, M.H. (2021). “Numerical linear algebra and optimization”, Book Series Name: Classics in Applied Mathematics, SIAM, doi: https://doi.org/10.1137/1.9781611976571.
[17] Glover, F. (1986). “Future paths for integer programming and links to artificial intelligence”, Computers & Operations Research, 13(5), 533-549, doi: https://doi.org/10.1016/0305-0548(86)90048-1.
[18] Goldberg, D.E. (1989). “Genetic algorithms in search, optimization, and machine learning”, Addison-Wesley Longman Publishing Co., Inc., doi: https://doi.org/10.5555/534133.
[19] Hager, W.W., Krylyuk, Y. (1999). “Graph partitioning and continuous quadratic programming”, SIAM Journal on Discrete Mathematics, 12(4), 500-523, doi: https://doi.org/10.1137/S0895480199335829.
[20] Hager, W.W., Phan, D.T., Zhang, H. (2013). “An exact algorithm for graph partitioning”, Mathematical Programming, 137(1), 531-556, doi: https://doi.org/10.1007/s10107-011-0503-x.
[21] Holland, J.H. (1975). “Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence”, Complex Adaptive Systems, University of Michigan Press, doi: https://doi.org/10.7551/mitpress/1090.001.0001.
[22] Johnson, E.L., Mehrotra, A., Nemhauser, G.L. (1993). “Min-cut clustering”, Mathematical Programming, 62, 133-151, doi: https://doi.org/10.1007/BF01585164.
[23] Kadluczka, P., Wala, K. (1995). “Tabu search and genetic algorithms for the generalized graph partitioning problem”, Control and Cybernetics, 24, 459-476.
[24] Kaufman, W.E., Krambeck, F.J., Prater, C.D., Weekman, V.W. (1977). “Automation and databases in an industrial laboratory”, IEEE Conference on Decision and Control including the 16th Symposium on Adaptive Processes and A Special Symposium on Fuzzy Set Theory and Applications, New Orleans, LA, 494-497, doi: https://doi.org/10.1109/CDC.1977.271623.
[25] Kernighan, B.W., Lin, S. (1970). “An efficient heuristic procedure for partitioning graphs”, The Bell System Technical Journal, 49(2), 291-307, doi: https://doi.org/10.1002/j.1538-7305.1970.tb01770.x.
[26] Kóczy, László T. (1992). “Fuzzy graphs in the evaluation and optimization of networks”, Fuzzy Sets and Systems, 46(3), 307-319, doi: https://doi.org/10.1016/0165-0114(92)90369-F.
[27] Kohmoto, K., Katayama, K., Narihisa, H. (2003). “Performance of a genetic algorithm for the graph partitioning problem”, Mathematical and Computer Modelling, 38(11-13), 1325-1332, doi: http://dx.doi.org/10.1016/S0895-7177(03)90134-8.
[28] Lawson, C.L., Hanson. R.J. (1995). “Solving least squares problems”, Society for Industrial and Applied Mathematics, SIAM, doi: https://doi.org/10.1137/1.9781611971217.
[29] Li, M., Chi, H., Zhou, C., Xu, S. (2020). “GAP: Genetic algorithm based large-scale graph partition in heterogeneous cluster”, IEEE Access, 8, 144197-144204, doi: https://doi.org/10.1109/ACCESS.2020.3014351.
[30] Lim, A., Chee, Y-M. (1991). “Graph partitioning using tabu search”, 1991 IEEE International Symposium on Circuits and Systems (ISCAS), Singapore, 2, 1164-1167, doi: https://doi.org/10.1109/ISCAS.1991.176574.
[31] Mahdavi-Amiri, N., Nasseri, S.H. (2007). “Duality results and a dual simplex method for linear programming problems with trapezoidal fuzzy variables”, Fuzzy Sets and Systems, 158(17), 1961-1978, doi: https://doi.org/10.1016/j.fss.2007.05.005.
[32] Pieter, M., Mouton, S. (2012). “Francis Guthrie: A colourful life”, The Mathematical Intelligencer, 34, 67-75, doi: https://doi.org/10.1007/s00283-012-9307-y.
[33] Michalewicz, Z. (2013). “Genetic algorithms + Data structures = Evolution programs”, SpringerVerlag Berlin Heidelberg, doi: https://doi.org/10.1007/978-3-662-03315-9.
[34] Panos, P., Birce B.B., Feyza, G., Ozgur, D., Birce, B. (2013). “Fuzzy combinatorial optimization problems”, Handbook of Combinatorial Optimization, 1357-1413, doi: http://dx.doi.org/10.1007/978-1-4419-7997-1_68.
[35] Pillai, S.U. Suel, T., Cha, S. (2005). “The Perron-Frobenius theorem: Some of its applications”, IEEE Signal Processing Magazine, 22(2), 62-75, doi: https://doi.org/10.1109/MSP.2005.1406483.
[36] Rosenfeld, A. (1975). “Fuzzy graphs”, Fuzzy Sets and their Applications to Cognitive and Decision Processes, Academic Press, 77-95, doi: https://doi.org/10.1016/B978-0-12-775260-0.50008-6.
[37] Sharma, P.D., Rallapalli, S., Lakkaniga, N.R. (2023). “An innovative approach for predicting pandemic hotspots in complex wastewater networks using graph theory coupled with fuzzy logic”, Stochastic Environmental Research and Risk Assessment, 37, 3639–3656, doi: https://doi.org/10.1007/s00477-023-02468-3.
[38] Shazely, S., Baraka, H., Abdel-Wahab, A. (1998). “Solving graph partitioning problem using genetic algorithms”, 1998 Midwest Symposium on Circuits and Systems (Cat. No. 98CB36268), Notre Dame, IN, USA, 302-305, doi: https://doi.org/10.1109/MWSCAS.1998.759492.
[39] Yager, R.R. (1981). “A procedure for ordering fuzzy subsets of the unit interval”, Information Sciences, 24(2), 143-161, doi: https://doi.org/10.1016/0020-0255(81)90017-7.
[40] Zadeh, L.A. (1976). “A fuzzy-algorithmic approach to the definition of complex or imprecise concepts”, International Journal of Man-Machine Studies, 8(3), 249-291, doi: https://doi.org/10.1016/S0020-7373(76)80001-6.
)