Optimizing linear functions over novel fuzzy relation equations: Structure, feasibility, and global solutions

Ghodousian, A.; Mollakazemiha, M.; Mashinchi, M.; Mesiar, R.

doi:10.22111/ijfs.2025.9295

Document Type : Research Paper

Authors

¹ School of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran.

² Department of Mathematics, Faculty of Mathematics and Computer Science, University of M¨ unster, M¨ unster, Germany.

³ Department of Statistics, Faculty of Mathematics and Computer, Shahid Bahonar University of Kerman, Kerman, Iran

⁴ Department of Mathematics, Faculty of Civil Engineering, Slovak University of Technology in Bratislava, Bratislava, Slovakia.

⁵ Palack´ y University Olomouc, Faculty of Science, Dept. Algebra and Geometry, 17. listopadu 12, 771 46 Olomouc, Czech Republic

https://doi.org/10.22111/ijfs.2025.9295

Abstract

We investigate the linear objective function optimization problem constrained by a new system of fuzzy relation
equations, utilizing the minimum t-norm for fuzzy compositions. Our findings reveal that the feasible region is
characterized as a finite union of closed convex cells. We provide necessary and sufficient conditions to determine
the problem’s feasibility. To streamline optimization, seven novel rules are proposed, on which an algorithm is based
to achieve a global optimum. Notably, a specific instance of our problem is shown to be equivalent to the well-known
minimal vertex cover problem. The efficacy of our algorithm is demonstrated through a concrete example.

Keywords

References

[1] C. W. Chang, B. S. Shieh, Linear optimization problem constrained by fuzzy max-min relation equations, Information Sciences, 234 (2013), 71-79. https://doi.org/10.1016/j.ins.2011.04.042

[2] L. Chen, P. P. Wang, Fuzzy relation equations (I): The general and specialized solving algorithms, Soft Computing, 6(5) (2002), 428-435. https://doi.org/10.1007/s00500-001-0157-3

[3] L. Chen, P. P. Wang, Fuzzy relation equations (II): The branch-point-solutions and the categorized minimal solutions, Soft Computing, 11(1) (2007), 33-40. https://doi.org/10.1007/s00500-006-0050-1

[4] M. Cornejo, D. Lobo, J. Medina, Bipolar fuzzy relation equations based on product t-norm, in: Proceedings of
2017 IEEE International Conference on Fuzzy Systems, 2017. https://doi.org/10.1109/FUZZ-IEEE.2017.
8015691

[5] S. Dempe, A. Ruziyeva, On the calculation of a membership function for the solution of a fuzzy linear optimization problem, Fuzzy Sets and Systems, 188(1) (2012), 58-67. https://doi.org/10.1016/j.fss.2011.07.014

[6] A. Di Nola, S. Sessa, W. Pedrycz, E. Sanchez, Fuzzy relational equations and their applications in knowledge
engineering, Dordrecht: Kluwer Academic Press, 1989. https://doi.org/10.1007/978-94-017-1650-5

[7] D. Dubey, S. Chandra, A. Mehra, Fuzzy linear programming under interval uncertainty based on IFS representation, Fuzzy Sets and Systems, 188(1) (2012), 68-87. https://doi.org/10.1016/j.fss.2011.09.008

[8] D. Dubois, H. Prade, An introduction to bipolar representations of information and preference, International
Journal of Intelligent Systems, 23(8) (2008), 866-877. https://doi.org/10.1002/int.20297

[9] D. Dubois, H. Prade, An overview of the asymmetric bipolar representation of positive and negative information
in possibility theory, Fuzzy Sets and Systems, 160 (2009), 1355-1366. https://doi.org/10.1016/j.fss.2008.
11.006

[10] Y. R. Fan, G. H. Huang, A. L. Yang, Generalized fuzzy linear programming for decision making under
uncertainty: Feasibility of fuzzy solutions and solving approach, Information Sciences, 241 (2013), 12-27.
https://doi.org/10.1016/j.ins.2013.04.004

[11] S. C. Fang, G. Li, Solving fuzzy relational equations with a linear objective function, Fuzzy Sets and Systems,
103(1) (1999), 107-113. https://doi.org/10.1016/S0165-0114(97)00184-X

[12] S. Freson, B. De Baets, H. De Meyer, Linear optimization with bipolar max-min constraints, Information
Sciences, 234 (2013), 3-15. https://doi.org/10.1016/j.ins.2011.06.009

[13] A. Ghodousian, Optimization of linear problems subjected to the intersection of two fuzzy relational inequalities
defined by Dubois-Prade family of t-norms, Information Sciences, 503 (2019), 291-306. https://doi.org/10.
1016/j.ins.2019.06.058

[14] A. Ghodousian, A. Babalhavaeji, An efficient genetic algorithm for solving nonlinear optimization problems
defined with fuzzy relational equations and max- Lukasiewicz composition, Applied Soft Computing, 69 (2018),
475-492. https://doi.org/10.1016/j.asoc.2018.04.029

[15] A. Ghodousian, E. Khorram, Fuzzy linear optimization in the presence of the fuzzy relation inequality constraints with max-min composition, Information Sciences, 178(2) (2008), 501-519. https://doi.org/10.1016/
j.ins.2007.07.022

[16] A. Ghodousian, E. Khorram, Linear optimization with an arbitrary fuzzy relational inequality, Fuzzy Sets and
Systems, 206 (2012), 89-102. https://doi.org/10.1016/j.fss.2012.04.009

[17] A. Ghodousian, M. Naeeimi, A. Babalhavaeji, Nonlinear optimization problem subjected to fuzzy relational
equations defined by Dubois-Prade family of t-norms, Computers and Industrial Engineering, 119 (2018), 167-
180. https://doi.org/10.1016/j.cie.2018.03.038

[18] A. Ghodousian, M. Raeisian Parvari, A modified PSO algorithm for linear optimization problem subject to the
generalized fuzzy relational inequalities with fuzzy constraints (FRI-FC), Information Sciences, 418-419 (2017),
317-345. https://doi.org/10.1016/j.ins.2017.07.032

[19] A. Ghodousian, F. Samie Yousefi, Linear optimization problem subjected to fuzzy relational equations and fuzzy
constraints, Iranian Journal of Fuzzy Systems, 20(2) (2023), 1-20. https://doi.org/10.22111/ijfs.2023.
7552

[20] F. F. Guo, L. P. Pang, D. Meng, Z. Q. Xia, An algorithm for solving optimization problems with fuzzy relational
inequality constraints, Information Sciences, 252 (2013), 20-31. https://doi.org/10.1016/j.ins.2011.09.
030

[21] S. M. Guu, Y. K. Wu, Minimizing a linear objective function with fuzzy relation equation constraints, Fuzzy
Optimization and Decision Making, 12 (2002), 1568-4539. https://doi.org/10.1023/A:1020955112523

[22] S. M. Guu, Y. K. Wu, Minimizing a linear objective function under a max-t-norm fuzzy relational equation
constraint, Fuzzy Sets and Systems, 161(2) (2010), 285-297. https://doi.org/10.1016/j.fss.2009.03.007

[23] K. Hirota, W. Pedrycz, Solving fuzzy relational equations through logical filtering, Fuzzy Sets and Systems,
81(3) (1996), 355-363. https://doi.org/10.1016/0165-0114(95)00221-9

[24] F. Kouchakinejad, M. Mashinchi, R. Mesiar, Solution-set invariant matrices and vectors in fuzzy relation
inequalities based on max aggregation function composition, Iranian Journal of Fuzzy Systems, 13(7) (2016),
91-100. https://doi.org/10.22111/ijfs.2016.2945

[25] H. C. Lee, S. M. Guu, On the optimal three-tier multimedia streaming services, Fuzzy Optimization and Decision
Making, 2(1) (2003), 31-39. https://doi.org/10.1023/A:1022848114005

[26] P. K. Li, S. C. Fang, On the resolution and optimization of a system of fuzzy relational equations with
sup-t composition, Fuzzy Optimization and Decision Making, 7 (2008), 169-214. https://doi.org/10.1007/
s10700-008-9029-y

[27] P. Li, Q. Jin, On the resolution of bipolar max-min equations, Kybernetika, 52(4) (2016), 514-530. https:
//dml.cz/bitstream/handle/10338.dmlcz/145903/Kybernetika_52-2016-4_2.pdf

[28] P. Li, Y. Liu, Linear optimization with bipolar fuzzy relational equation constraints using Lukasiewicz triangular
norm, Soft Computing, 18 (2014), 1399-1404. https://doi.org/10.1007/s00500-013-1152-1

[29] J. X. Li, S. J. Yang, Fuzzy relation inequalities about the data transmission mechanism in bittorrent-like peer-topeer file sharing systems, in: Proceedings of the 9th International Conference on Fuzzy Systems and Knowledge
discovery (FSKD 2012), 452-456. https://doi.org/10.1109/FSKD.2012.6233956

[30] J. L. Lin, On the relation between fuzzy max-Archimedean t-norm relational equations and the covering problem,
Fuzzy Sets and Systems, 160(16) (2009), 2328-2344.https://doi.org/10.1016/j.fss.2009.01.012 .

[31] J. L. Lin, Y. K. Wu, S. M. Guu, On fuzzy relational equations and the covering problem, Information Sciences,
181(14) (2011), 2951-2963. https://doi.org/10.1016/j.ins.2011.03.004

[32] C. C. Liu, Y. Y. Lur, Y. K. Wu, Linear optimization of bipolar fuzzy relational equations with max- Lukasiewicz
composition, Information Sciences, 360 (2016), 149-162. https://doi.org/10.1016/j.ins.2016.04.041

[33] J. Loetamonphong, S. C. Fang, Optimization of fuzzy relation equations with max-product composition, Fuzzy
Sets and Systems, 118(3) (2001), 509-517. https://doi.org/10.1016/S0165-0114(98)00417-5

[34] J. Lu, S. C. Fang, Solving nonlinear optimization problems with fuzzy relation equations consraints, Fuzzy Sets
and Systems, 119(1) (2001), 1-20. https://doi.org/10.1016/S0165-0114(98)00471-0

[35] A. V. Markovskii, On the relation between equations with max-product composition and the covering problem,
Fuzzy Sets and Systems, 153(2) (2005), 261-273. https://doi.org/10.1016/j.fss.2005.02.010

[36] M. Mizumoto, H. J. Zimmermann, Comparison of fuzzy reasoning method, Fuzzy Sets and Systems, 8(3) (1982),
253-283. https://doi.org/10.1016/S0165-0114(82)80004-3

[37] W. Pedrycz, Fuzzy relational equations with generalized connectives and their applications, Fuzzy Sets and
Systems, 10(1-3) (1983), 185-201. https://doi.org/10.1016/S0165-0114(83)80114-6

[38] W. Pedrycz, Granular computing: Analysis and design of intelligent systems, CRC Press, Boca Raton, 2013.

[39] K. Peeva, Y. Kyosev, Fuzzy relational calculus: Theory, applications and software, World Scientific Publishing
Co Pte Ltd, 2005.

[40] X. B. Qu, X. P. Wang, Minimization of linear objective functions under the constraints expressed by a system of
fuzzy relation equations, Information Sciences, 178(17) (2008), 3482-3490. https://doi.org/10.1016/j.ins.
2008.04.004

[41] X. B. Qu, X. P. Wang, M. H. Lei, Conditions under which the solution sets of fuzzy relational equations over
complete Brouwerian lattices form lattices, Fuzzy Sets and Systems, 234 (2014), 34-45. https://doi.org/10.
1016/j.fss.2013.03.017

[42] E. Sanchez, Resolution of Eigen fuzzy sets equations, Fuzzy Sets and Systems, 1(1) (1978), 69-75. https:
//doi.org/10.1016/0165-0114(78)90033-7

[43] E. Sanchez, Solution in composite fuzzy relation equations: Application to medical diagnosis in Brouwerian
logic, in: M.M. Gupta. G.N. Saridis, B.R. Games (Eds.), Readings in Fuzzy Sets for Intelligent Systems, (1993),
159-165. https://doi.org/10.1016/B978-1-4832-1450-4.50017-1

[44] B. S. Shieh, Infinite fuzzy relation equations with continuous t-norms, Information Sciences, 178(8) (2008),
1961-1967. https://doi.org/10.1016/j.ins.2007.12.006

[45] B. S. Shieh, Minimizing a linear objective function under a fuzzy max-t-norm relation equation constraint,
Information Sciences, 181(4) (2011), 832-841. https://doi.org/10.1016/j.ins.2010.10.024

[46] G. B. Stamou, S. G. Tzafestas, Resolution of composite fuzzy relation equations based on Archimedean triangular
norms, Fuzzy Sets and Systems, 120(3) (2001), 395-407. https://doi.org/10.1016/S0165-0114(99)00117-7

[47] F. Sun, Conditions for the existence of the least solution and minimal solutions to fuzzy relation equations
over complete Brouwerian lattices, Information Sciences, 205 (2012), 86-92. https://doi.org/10.1016/j.
ins.2012.04.002

[48] F. Sun, X. P. Wang, X. B. Qu, Minimal join decompositions and their applications to fuzzy relation equations
over complete Brouwerian lattices, Information Sciences, 224 (2013), 143-151. https://doi.org/10.1016/j.
ins.2012.10.038

[49] Y. K. Wu, Optimization of fuzzy relational equations with max-av composition, Information Sciences, 177(19)
(2007), 4216-4229. https://doi.org/10.1016/j.ins.2007.02.037

[50] Y. K. Wu, S. M. Guu, Minimizing a linear function under a fuzzy max-min relational equation constraints,
Fuzzy Sets and Systems, 150(1) (2005), 147-162.

[51] Y. K. Wu, S. M. Guu, An efficient procedure for solving a fuzzy relation equation with max-Archimedean t-norm
composition, IEEE Transactions on Fuzzy Systems, 16 (2008), 73-84.

[52] Y. K. Wu, S. M. Guu, J. Y. Liu, Reducing the search space of a linear fractional programming problem under
fuzzy relational equations with max-Archimedean t-norm composition, Fuzzy Sets and Systems, 159(24) (2008),
3347-3359. https://doi.org/10.1016/j.fss.2008.04.007
Optimizing linear functions over novel fuzzy relation equations: Structure, feasibility, and global solutions
179

[53] Q. Q. Xiong, X. P. Wang, Fuzzy relational equations on complete Brouwerian lattices, Information Sciences,
193 (2012), 141-152. https://doi.org/10.1016/j.ins.2011.12.030

[54] S. J. Yang, An algorithm for minimizing a linear objective function subject to the fuzzy relation inequalities
with addition-min composition, Fuzzy Sets and Systems, 255 (2014), 41-51. https://doi.org/10.1016/j.fss.
2014.04.007

[55] X. P. Yang, Resolution of bipolar fuzzy relation equations with max-Lukasiewicz composition, Fuzzy Sets and
Systems, 397 (2020), 41-60. https://doi.org/10.1016/j.fss.2019.08.005

[56] X. P. Yang, X. G. Zhou, B. Y. Cao, Latticized linear programming subject to max-product fuzzy relation
inequalities with application in wireless communication, Information Sciences, 358-359 (2016), 44-55. https:
//doi.org/10.1016/j.ins.2016.04.014

[57] J. Zhou, Y. Yu, Y. Liu, Y. Zhang, Solving nonlinear optimization problems with bipolar fuzzy relational
equations constraints, Journal of Inequalities and Applications, 126 (2016), 1-10. https://doi.org/10.1186/
s13660-016-1056-6

Optimizing linear functions over novel fuzzy relation equations: Structure, feasibility, and global solutions

References

References

Volume 22, Issue 3May and June 2025Pages 151-179

Volume 22, Issue 3
May and June 2025
Pages 151-179