In collaboration with Payame Noor University and the Iranian Society of Instrumentation and Control Engineers

Document Type : Research Article

Authors

1 Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad 91775, Iran

2 Mosaheb Institute of Mathematics, Kharazmi University, Tehran, Iran

Abstract

This paper considers a fuzzy graph k-partitioning problem in which both edge and vertex weights are modeled by trapezoidal fuzzy numbers. To avoid nonlinear operations that are not closed within the trapezoidal family, the fuzzy inputs are first mapped to scalar values using Yager’s linear ranking function, and pairwise vertex-weight dissimilarities are then formed in the ranked space. On this basis, we develop a randomized exchange heuristic that preserves the prescribed partition sizes and evaluates each candidate move through an explicit gain formula. For a symmetric ranked matrix with a zero diagonal, the auxiliary matrix can be updated in closed form, which gives a direct monotonicity result and reduces the cost of an attempted exchange to O(n) after O(n2) preprocessing. The method is evaluated over 15 independent runs on instances with n = 20, 1000, and 1500 vertices and is compared with a genetic algorithm (GA), Tabu search (TS), sequential least squares programming (SLSQP), and a Kernighan–Lin/Fiduccia–Mattheyses (KL/FM)-type baseline. On the two larger instances, the proposed method attains the highest mean objective value and the lowest mean runtime among the five methods; the paired comparisons against GA, TS, and SLSQP remain significant after Holm–Bonferroni correction and are supported by two-sided Wilcoxon signed-rank tests. On the smallest instance (n = 20), TS with tenure 15 and full cross-partition enumeration (NTS = 190 candidate pairs) attains a higher mean objective than the proposed method. A supplementary sensitivity study examines the main GA and TS parameters and the trade-off parameter θ.

Highlights

  • Extends fuzzy graph bipartitioning to general k-partitioning with fuzzy edge AND vertex weights.
  • Converts the fuzzy quadratic model to a crisp equivalent using Yager's linear ranking function.
  • Proposes a monotone move-based heuristic with a closed-form update rule for candidate moves.
  • Proves theoretically that the ranked objective value is nondecreasing at every accepted move.
  • Reports lower CPU time than Genetic Algorithm and Tabu Search on graphs up to 1500 vertices.

Keywords

Main Subjects

[1] Abouyee Mehrizi, A., Ghanbari, R., Sadeghi, S., Ghorbani-Moghadam, K. (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, 165, 112109. https://doi.org/10.1016/j.asoc. 2024.112109
[2] Adoni, W. Y. H., Nahhal, T., Krichen, M., Aghezzaf, B., Elbyed, A. (2020). “A survey of current challenges in partitioning and processing of graph-structured data in parallel and distributed systems”. Distributed and Parallel Databases, 38, 495–530. https://doi. org/10.1007/s10619-020-07294-y
[3] Adoni, W. Y. H., Nahhal, T., Krichen, M., El Byed, A., Assayad, I. (2020). “DHPV: A distributed algorithm for large-scale graph partitioning”. Journal of Big Data, 7, 76. https://doi.org/10.1186/s40537-020-00357-y
[4] Alsaeedi, M., Tavakoli, M., Abouyee Mehrizi, A., Ghorbani Moghadam, K., Ghanbari, R. (2025). “Solution techniques for fuzzy graph partitioning based on heuristic optimization”. Control and Optimization in Applied Mathematics, 10(2), 273–293. https://doi.org/ 10.30473/coam.2025.74009.1296
[5] Belotti, P., Buchanan, A., Ezazipour, S. (2025). “Political districting to optimize the Polsby–Popper compactness score with application to voting rights”. Operations Research, 73(5), 2330–2350. https://doi.org/10.1287/opre.2024.1078
[6] Bichot, C.-E., Siarry, P. (Eds.). (2011). “Graph partitioning”. ISTE Ltd./John Wiley & Sons. ISBN: 978-1-84821-233-6. https://doi.org/10.1002/9781118601181
[7] Cheng, T., Zeng, G., Wang, S. (2025). “A balanced partitioning method for big graphs via coarsen-partition-refining steps with preserving atomic subgraphs”. Concurrency and Computation: Practice and Experience, 37(25–26), e70304. https://doi.org/10. 1002/cpe.70304
[8] Dubois, D., Prade, H. (1978). “Operations on fuzzy numbers”. International Journal of Systems Science, 9(6), 613–626. https://doi.org/10.1080/00207727808941724
[9] Firouzian, S., Adabitabar Firozja, M. (2016). “Fuzzy number-valued fuzzy graph”. Control and Optimization in Applied Mathematics, 1(2), 77–86. https://mathco. journals.pnu.ac.ir/article_3400.html
[10] Garey, M. R., Johnson, D. S., Stockmeyer, L. (1976). “Some simplified NP-complete graph problems”. Theoretical Computer Science, 1(3), 237–267. https://doi.org/10. 1016/0304-3975(76)90059-1
[11] George, A. (1973). “Nested dissection of a regular finite element mesh”. SIAM Journal on Numerical Analysis, 10(2), 345–363. https://doi.org/10.1137/0710032
[12] Gilbert, J. R., Miller, G. L., Teng, S.-H. (1998). “Geometric mesh partitioning: Implementation and experiments”. SIAM Journal on Scientific Computing, 19(6), 2091–2110. https://doi.org/10.1137/S106482759631031X
[13] Gutiérrez García-Pardo, I., Barroso Pérez, M., Gómez González, D., Castro Cantalejo, J. (2025). “Improving community detection algorithms in directed graphs with fuzzy measures: An application to mobility networks”. Expert Systems with Applications, 269, 126305. https://doi.org/10.1016/j.eswa.2024.126305
[14] Hager, W. W., Krylyuk, Y. (1999). “Graph partitioning and continuous quadratic programming”. SIAM Journal on Discrete Mathematics, 12(4), 500–523. https://doi.org/10. 1137/S0895480199335829
[15] Hager, W. W., Krylyuk, Y. (2002). “Multiset graph partitioning”. Mathematical Methods of Operations Research, 55(1), 1–10. https://doi.org/10.1007/s001860200173
[16] Inuiguchi, M., Gao, Z., Henriques, C. O. (2023). “Robust optimality analysis of nondegenerate basic feasible solutions in linear programming problems with fuzzy objective coefficients”. Fuzzy Optimization and Decision Making, 22(1), 51–79. https://doi. org/10.1007/s10700-022-09383-2
[17] Karypis, G., Kumar, V. (1998). “A fast and high quality multilevel scheme for partitioning irregular graphs”. SIAM Journal on Scientific Computing, 20(1), 359–392. https://doi. org/10.1137/S1064827595287997
[18] Kernighan, B. W., Lin, S. (1970). “An efficient heuristic procedure for partitioning graphs”. The Bell System Technical Journal, 49(2), 291–307. https://doi.org/10. 1002/j.1538-7305.1970.tb01770.x
[19] Khan, I. U., Aamir, M., Ullah, M., Shah, M. S. (2024). “Fuzzy neural network for fuzzy quadratic programming with penalty function and mean-variance Markowitz portfolio model”. Applied Computational Intelligence and Soft Computing, 2024, 8694583. https://doi.org/10.1155/2024/8694583
[20] Lu, Z., Chen, L., Gao, J., Hao, J.-K. (2026). “Multilevel iterated tabu search for the multi-constraint graph partitioning problem”. Computers & Operations Research, 189, 107389. https://doi.org/10.1016/j.cor.2026.107389
[21] Maas, N., Gottesbüren, L., Seemaier, D. (2024). “Parallel unconstrained local search for partitioning irregular graphs”. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), 32–45. https://doi.org/10.1137/ 1.9781611977929.3
[22] 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. https://doi.org/10.1016/j.fss.2007.03.018
[23] Popa, L. (2023). “A new ranking method for trapezoidal intuitionistic fuzzy numbers and its application to multi-criteria decision making”. International Journal of Computers Communications & Control, 18(2), 5118. https://doi.org/10.15837/ijccc.2023. 2.5118
[24] Rolland, E., Pirkul, H., Glover, F. (1996). “Tabu search for graph partitioning”. Annals of Operations Research, 63, 209–232. https://doi.org/10.1007/BF02125425
[25] Rosenfeld, A. (1975). “Fuzzy graphs”. In L. A. Zadeh, K.-S. Fu, K. Tanaka, M. Shimura (Eds.), Fuzzy Sets and Their Applications to Cognitive and Decision Processes, 77–95. Academic Press. https://doi.org/10.1016/B978-0-12-775260-0.50008-6
[26] Sun, W., Liu, H., Wang, X. (2025). “Multi-constraint graph partitioning problems via recursive bipartition algorithm based on subspace minimization conjugate gradient method”. Journal of Applied Mathematics and Computing, 71(Suppl 1), 1289–1315. https://doi. org/10.1007/s12190-025-02528-7
[27] Yager, R. R. (1981). “A procedure for ordering fuzzy subsets of the unit interval”. Information Sciences, 24(2), 143–161. https://doi.org/10.1016/0020-0255(81)90017-7
[28] Yager, R. R., Filev, D. (1999). “On ranking fuzzy numbers using valuations”. International Journal of Intelligent Systems, 14(12), 1249–1268. https://doi.org/10.1002/(SICI)1098-111X(199912)14:12<1249::AID-INT6>3.0.CO;2-#
[29] Yu, Q., Li, W., Yang, D., Zhang, H. (2021). “Partitioning urban road network based on travel speed correlation”. International Journal of Transportation Science and Technology, 10(2), 97–101. https://doi.org/10.1016/j.ijtst.2020.07.001
[30] Zadeh, L. A. (1965). “Fuzzy sets”. Information and Control, 8(3), 338–353. https://doi.org/10.1016/S0019-9958(65)90241-X