Abstract
This work considers solving the sup-\({\mathcal{T}}\) equation constrained optimization problems from the integer programming viewpoint. A set covering-based surrogate approach is proposed to solve the sup-\({\mathcal{T}}\) equation constrained optimization problem with a separable and monotone objective function in each of the variables. This is our first trial of developing integer programming-based techniques to solve sup-\({\mathcal{T}}\) equation constrained optimization problems. Our computational results confirm the efficiency of the proposed method and show its potential for solving large scale sup-\({\mathcal{T}}\) equation constrained optimization problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abbasi Molai A., Khorram E. (2007) A modified algorithm for solving the proposed models by Ghodousian and Khorram and Khorram and Ghodousian. Applied Mathematics and Computation 190: 1161V1167
Abbasi Molai A., Khorram E. (2008) An algorithm for solving fuzzy relation equations with max-T composition operator. Information Sciences 178(5): 1293–1308
Balas E., Carrera M. C. (1996) A dynamic subgradient-based branch and bound procedure for set covering. Operations Research 44: 875–890
Balas E., Ho A. (1980) Set covering algorithms using cutting planes, heuristics and subgradient optimization: A computational study. Mathematical Programming 12: 37–60
Beasley J. E. (1987) An algorithm for the set covering problem. European Journal of Operational Research 31: 85–93
Beasley J. E. (1990) A Lagrangian heuristic for the set covering problem. Naval Research Logistics 37: 151–164
Beasley J. E., Chu P. C. (1996) A genetic algorithm for the set covering problem. European Journal of Operational Research 94: 392–404
Blyth T. S., Janowitz M. F. (1972) Residuation Theory. Pergamon Press, Oxford
Caprara A., Toth P., Fischetti M. (2000) Algorithms for the set covering problem. Annals of Operations Research 98: 353–371
Di Nola A., Sessa S., Pedrycz W., Sanchez E. (1989) Fuzzy relation equations and their applications to knowledge engineering. Kluwer, Dordrecht, Netherlands
Elbassioni K. M. (2008) A note on systems with max-min and max-product constraints. Fuzzy Sets and Systems 159: 2272–2277
Fang S.-C., Li G. (1999) Solving fuzzy relation equations with a linear objective function. Fuzzy Sets and Systems 103(1): 107–113
Fisher M. L., Kedia P. (1990) Optimal solutions of set covering/partitioning problems using dual heuristics. Management Science 36: 674–688
Ghodousian A., Khorram E. (2006) An algorithm for optimizing the linear function with fuzzy relation equation constraints regarding max-prod composition. Applied Mathematics and Computation 178(2): 502–509
Golumbic M. C., Hartman I. B.-A. (2005) Graph theory, combinatorics and algorithms: Interdisciplinary applications. Springer, New York
Guu S. M., Wu Y. K. (2002) Minimizing a linear objective function with fuzzy relation equation constraints. Fuzzy Optimization and Decision Making 1(4): 347–360
Held M., Wolfe P., Crowder H. P. (1974) Validation of subgradient optimization. Mathematical Programming 6: 62–88
Khachiyan L., Boros E., Elbassioni K., Gurvich V. (2006) An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation. Discrete Applied Mathematics 154: 2350–2372
Khorram E., Ghodousian A. (2006) Linear objective function optimization with fuzzy relation equation constraints regarding max-av composition. Applied Mathematics and Computation 173(2): 872–886
Klement E. P., Mesiar R., Pap E. (2000) Triangular norms. Kluwer, Dordrecht
Li, P., Fang, S.-C. & Zhang, X. (2008). Nonlinear optimization subject to a system of fuzzy relational equations with max-min composition. In Proceedings of the seventh international symposium of operations research and its applications, Lijiang, China, pp. 1–9.
Li P., Fang S.-C. (2008) On the resolution and optimization of a system of fuzzy relational equations with sup-\({\mathcal{T} }\) composition. Fuzzy Optimization and Decision Making 7(2): 169–214
Li P., Fang S.-C. (2009) A survey on fuzzy relational equations, Part I: classification and solvability. Fuzzy Optimization and Decision Making 8: 179–229
Li P., Fang S.-C. (2009) Latticized linear optimization on the unit interval. IEEE Transactions on Fuzzy Systems 17: 1353–1365
Loetamonphong J., Fang S.-C., Young R. (2002) Multi-objective optimization problems with fuzzy relation equation constraints. Fuzzy Sets and Systems 127(2): 141–164
Loetamonphong J., Fang S.-C. (2001) Optimization of fuzzy relation equations with max-product composition. Fuzzy Sets and Systems 118(3): 509–517
Lopes F. B., Lorena L. A. (1994) Surrogate heuristic for set covering problems. European Journal of Operational Research 79: 138–150
Lorena, L. A. N. & Plateau, G. (1988) A monotone decreasing algorithm for the 0-1 multiknapsack dual problem, Rapport de recherche L.I.P.N. 89-1, Université Paris-Nord, France.
Lu J., Fang S.-C. (2001) Solving nonlinear optimization problems with fuzzy relation equation constraints. Fuzzy Sets and Systems 119(1): 1–20
Markovskii A. (2005) On the relation between equations with max-product composition and the covering problem. Fuzzy Sets and Systems 153(2): 261–273
Nemhauser K., Wolsey L. A. (1988) Integer and combinatorial optimization. Wiley, New York
Parker R. G. (1988) Discrete optimization. Academic Press, New York
Pedrycz W. (1985) On generalized fuzzy relational equations and their applications. Journal of Mathematical Analysis and Applications 107: 520–536
Peeva K., Kyosev Y. (2004) Fuzzy relational calculus: Theory, applications, and software. World Scientific, New Jersey
Sanchez E. (1976) Resolution of composite fuzzy relation equations. Information and Control 30(1): 38–48
Sanchez E. (1977) Solutions in composite fuzzy relation equations: Application to medical diagnosis in Brouwerian logic. In: Gupta M. M., Saridis G. N., Gaines B. R. (eds) Fuzzy automata and decision processes. North-Holland, Amsterdam, pp 221–234
Shieh B. S. (2010) A note on a paper by Molai and Khorram. Applied Mathematics and Computation 216: 3419–3422
Wang H. F. (1995) A multi-objective mathematical programming problem with fuzzy relation constraints. Journal of Multi-Criteria Decision Analysis 4(1): 23–35
Wang P. Z., Zhang D. Z., Sanchez E., Lee E. S. (1991) Latticized linear programming and fuzzy relation inequalities. Journal of Mathematical Analysis and Applications 159(1): 72–87
Wu Y. K., Guu S. M., Liu J. Y. C. (2002) An accelerated approach for solving fuzzy relation equations with a linear objective function. IEEE Transactions on Fuzzy Systems 10(4): 552–558
Wu Y. K., Guu S. M. (2004) A note on fuzzy relation programming problems with max-strict-t-norm composition. Fuzzy Optimization and Decision Making 3(3): 271–278
Wu Y. K., Guu S. M. (2005) Minimizing a linear function under a fuzzy max- min relational equation constraint. Fuzzy Sets and Systems 150(1): 147–162
Yang, J. H. & Cao, B. Y. (2007). Posynomial fuzzy relation geometric programming. In: Melin, P., Castillo, O., Aguilar, L. T., Kacprzyk, J., Pedrycz, W. (eds.), Proceedings of the 12th international fuzzy systems association world congress, Cancun, Mexico, pp. 563–572.
Yang, J. H. & Cao, B. Y. (2005). Geometric programming with fuzzy relation equation constraints. in proceedings of the ieee international conference on fuzzy systems, Reno, NV, pp. 557–560.
Zimmermann K. (2007) A note on a paper by E. Khorram and A. Ghodousian. Applied Mathematics and Computation 188: 244–245
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the National Science Council (NSC) of R.O.C., under Grant NSC 99-2918-I-214-001.
Rights and permissions
About this article
Cite this article
Hu, CF., Fang, SC. Set covering-based surrogate approach for solving sup-\({\mathcal{T}}\) equation constrained optimization problems. Fuzzy Optim Decis Making 10, 125–152 (2011). https://doi.org/10.1007/s10700-011-9099-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10700-011-9099-0