Separable programming problems with the max-product fuzzy relation equation constraints

Document Type : Original Manuscript


School of Mathematics and Computer Sciences, Damghan University, P.O.Box 36715-364, Damghan, Iran


In this paper, the separable programming problem subject to Fuzzy Relation Equation (FRE) constraints is studied. It is decomposed to two subproblems with decreasing and increasing objective functions with the same constraints. They are solved by the maximum solution and one of minimal solutions of its feasible domain, respectively. Their combination produces the original optimal solution. The detection of the optimal solution of the second subproblem by finding all the minimal solutions will be very time-consuming because of its NP-hardness. To overcome such difficulty, two types of sufficient conditions are proposed to find some of its optimal components or all of them. Under the first type sufficient conditions, some procedures are given to simplify the original problem. Also, a value matrix is defined and an algorithm is proposed to compute an initial upper bound on its optimal objective value using the matrix. Then, a branch-and-bound method is extended using the matrix and initial upper bound to solve the simplified problem without finding all the minimal solutions. 


[1] A.AbbasiMolai, A new algorithm for resolution of the quadratic programming problem with fuzzy relation inequality constraints, Computers & Industrial Engineering, 72 (2014), 306–314.
[2] A. Abbasi Molai, The quadratic programming problem with fuzzy relation inequality constraints, Computers & Industrial Engineering, 62(2012), 256–263.
[3] S. Aliannezhadi, A. Abbasi Molai, B. Hedayatfar, Linear optimization with bipolar max-parametric hamacher fuzzy relation equation constraints, Kybernetika, 52(4) (2016), 531-557.
[4] M. Allame, B. Vatankhahan, Iteration algorithm for solving Ax = b in max–min algebra, Applied Mathematics and Computation, 175 (2006), 269–276.
[5] T. Arnould, S. Tano, A rule-based method to calculate exactly the widest solution sets of a max–min fuzzy relational inequality, Fuzzy Sets and Systems, 64 (1994), 39–58.
[6] T. Arnould, S. Tano, Arule-based method to calculate the widest solution sets of a max–min fuzzy relational equation, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2 (1994), 247–256.
[7] M. M. Bourke, D. G. Fisher, Solution algorithms for fuzzy relational equations with max-product composition, Fuzzy Sets and Systems, 94 (1998), 61–69.
[8] C. W. Chang, B. S. Shieh, Linear optimization problem constrained by fuzzy max–min relation equations, Information Sciences, 234 (2013), 71–79.
[9] L. Chen, P. P. Wang, Fuzzy relation equations (I): The general and specialized solving algorithms, Soft Computing, 6 (2002), 428–435.
[10] L. Chen, P. P. Wang, Fuzzy relation equations(II): The branch-poit-solutions and the categorized minimal solutions, Soft Computing, 11(2007), 33–40.
[11] B. De Baets, Analytical solution methods for fuzzy relational equations, In: D. Dubois, H. Prade (Eds.), Fundamentals of Fuzzy Sets, The Handbooks of Fuzzy Sets Series. Kluwer Academic Publishers, Dordrecht, 2000.
[12] A. Di Nola, W. Pedrycz, S. Sessa, On solution of fuzzy relational equations and their characterization, BUSEFAL, 12 (1982), 60–71.
[13] A. Di Nola, W. Pedrycz, S. Sessa, P. Z. Wang, Fuzzy relation equations under triangular norms: a survey and new results, Stochastica, 8 (1984), 99–145.
[14] S. C. Fang, G. Li, Solving fuzzy relation equations with a linear objective function, Fuzzy Sets and Systems, 103 (1999), 107–113.
[15] S. M. Guu, Y. K. Wu, Minimizing a linear objective function with fuzzy relation equation constraints, Fuzzy Optimization and Decision Making, 1(4) (2002), 347–360.
[16] R. Hassanzadeh, E. Khorram, I. Mahdavi, N. Mahdavi-Amiri, A genetic algorithm for optimization problems with fuzzy relation constraints using max-product composition, Applied Soft Computing, 11 (2011), 551–560.
[17] E. Khorram, R. Hassanzadeh, Solving nonlinear optimization problems subjected to fuzzy relation equation constraints with max–average composition using a modified genetic algorithm, Computers & Industrial Engineering, 55 (2008), 1–14.
[18] C. Lichun, P. Boxing, The fuzzy relation equation with union or intersection preserving operator, Fuzzy Sets and Systems, 25(1988), 191–204.
[19] J. Loetamonphong, S. C. Fang, Optimization of fuzzy relation equations with max-product composition, Fuzzy Sets and Systems, 118 (2001), 509–517.
[20] J. Lu, S. C. Fang, Solving nonlinear optimization problems with fuzzy relation equations constraints, Fuzzy Sets and Systems, 119 (2001), 1–20.
[21] L. Luoh, W. J. Wang, Y. K. Liaw, New algorithms for solving fuzzy relation equations, Mathematics and Computers in Simulation, 59 (2002), 329–333.
[22] A. Markovskii, On the relation between equations with max-product composition and the covering problem, Fuzzy Sets and Systems, 153 (2005), 261–273.
[23] A. Markovskii, Solution of fuzzy equations with max-product composition in inverse control and decision making problems, Automation and Remote Control, 65 (2004), 1486–1495.
[24] K. Peeva, Systems of fuzzy equations and inequalities for fuzzy optimization, In: M. Delgado, J. Kacprzky, J. L. Verdegay, M. A. Vila (Eds.), Fuzzy Optimization, Recent Advances, Physica-Verlag, New York, 1994.
[25] E. Sanchez, Resolution of composite fuzzy relation equation, Information and Control, 30 (1976), 38–48.
[26] E. Sanchez, Solutions in composite fuzzy relation equations: application to medical diagnosis in Brouwerian logic, In: Fuzzy automata and decision processes (M. M. Gupta, G. N. Saridis, B. R. Gaines, Eds.), Amsterdam: NorthHolland, 1977.
[27] E. Shivanian, E. Khorram, Monomial geometric programming with fuzzy relation inequality constraints with maxproduct composition, Computers & Industrial Engineering, 56 (2009), 1386–1392.
[28] P.Z. Wang, D. Z. Zhang, E. Sanchez, E. S. Lee, Latticized linear programming and fuzzy relation inequalities, Journal of Mathematical Analysis and Applications, 159 (1991), 72–87.
[29] Y.-K. Wu, Optimization of fuzzy relational equations with max-av composition, Information Sciences, 177(2007), 4216–4229.
[30] Y. K. Wu, S. M. Guu, A note on fuzzy relation programming problems with max-strict-t-norm composition, Fuzzy Optimization and Decision Making, 3(3) (2004), 271–278.
[31] Y. K. Wu, S. M. Guu, Minimizing a linear function under a fuzzy max–min relational equation constraint, Fuzzy Sets and Systems, 150 (2005), 147–162.
[32] Y. K. Wu, S. M. Guu, J. Y. C. Liu, An accelerated approach for solving fuzzy relation equations with a linear objective function, IEEE Transactions on Fuzzy Systems, 10(4) (2002), 552–558.
[33] Y. K. Wu, S. M. Guu, J. Y. C. 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 (2008), 3347–3359.
[34] 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.
[35] X. P. Yang, X. G. Zhou, B. Y. Cao, Single-variable term semi-latticized fuzzy relation geometric programming with max-product operator, Information Sciences, 325 (2015), 271–287.
[36] X. G. Zhou, R. Ahat, Geometric programming problem with single-term exponents subject to max-product fuzzy relational equations, Mathematical and Computer Modelling, 53 (2011), 55–62.
[37] X. G. Zhou, X. P. Yang, B. Y. Cao, Posynomial geometric programming problem subject to max–min fuzzy relation equations, Information Sciences, 328 (2016), 15–25.