Possibilistic max-mean dispersion problem

Document Type : Research Paper

Authors

1 Facultad de Innovacion y Tecnologia, Universidad Del pacifico, Km. 7.5 Via a la Costa, Guayaquil - Ecuador

2 Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB, T6R 2V4, Canada.

Abstract

The Max-Mean Dispersion Problem comprises selecting a subset of elements from a set while maximising the average of a measure of dispersion. We usually compute this measure of dispersion based on some distance metric between the elements of the candidate set. However, in real-world applications, this measure of dispersion could be ill-defined or vague. For example, consider the problem of building a team to execute some kinds of project. We can see the dispersion between the members of the team as the team chemistry, so the coach is interested in maximising this chemistry. In this example, it would be very difficult to compute exactly a dispersion measure for each candidate. This is due to the lack of information about how well the candidates worked together in the past. To cope with imprecise or vague information, in this paper, we propose three mixed integer linear programming models based on possibility, necessity, and credibility measures. To the best of our knowledge, this is the first approach which explicitly considers this type of uncertainty in this optimisation problem.

Keywords

References

[1] R. E. Bellman, L. A. Zadeh, Decision-making in a fuzzy environment, Management Science, 17(4) (1970), B-141.
[2] G. Bortolan, R. Degani, A review of some methods for ranking fuzzy subsets, Fuzzy Sets and Systems, 15(1) (1985), 1-19.
[3] J. Brimberg, N. Mladenović, R. Todosijević, D. Urošević, Less is more: Solving the max-mean diversity problem with variable neighborhood search, Information Sciences, 382 (2017), 179-200.
[4] R. Carrasco, A. Pham, M. Gallego, F. Gortázar, R. Martí, A. Duarte, Tabu search for the max-mean dispersion problem, Knowledge-Based Systems, 85 (2015), 256-264.
[5] A. Charnes, W. W. Cooper, Chance-constrained programming, Management Science, 6(1) (1959), 73-79.
[6] T. Cura, M. Ozdemir, A new use of the ant system algorithm for the max-mean dispersion problem, Computers and Industrial Engineering, 135 (2019), 628-642.
[7] S. K. De, I. Beg, Triangular dense fuzzy sets and new defuzzification methods, Journal of Intelligent and Fuzzy Systems, 31(1) (2016), 469-477.
[8] F. Della Croce, M. Garraffa, F. Salassa, A hybrid three-phase approach for the max-mean dispersion problem, Computers and Operations Research, 71 (2016), 16-22.
[9] D. Dubois, Possibility theory and statistical reasoning, Computational Statistics and Data Analysis, 51(1) (2006), 47-69.
[10] D. J. Dubois, H. Prade, Fuzzy sets and systems: Theory and applications, 144, Academic Press, 1980.
[11] D. Dubois, H. Prade, Ranking fuzzy numbers in the setting of possibility theory, Information Sciences, 30(3) (1983), 183-224.
[12] D. Dubois, H. Prade, Possibility theory: An approach to computerized processing of uncertainty, Springer Science and Business Media, 1988.
[13] A. Ebrahimnejad, J. L. Verdegay, A survey on models and methods for solving fuzzy linear programming problems, In Fuzzy Logic in Its 50th Year, Springer, 2016, pages 327-368.
[14] M. Gallego, M. Laguna, R. Martí, A. Duarte, Tabu search with strategic oscillation for the maximally diverse grouping problem, Journal of the Operational Research Society, 64(5) (2013), 724-734.
[15] M. Garraffa, F. Della Croce, F. Salassa, An exact semidefinite programming approach for the max-mean dispersion problem, Journal of Combinatorial Optimization, 34(1) (2017), 71-93.
[16] J. B. Ghosh, Computational aspects of the maximum diversity problem, Operations Research Letters, 19(4) (1996), 175-181.
[17] F. Glover, C. C. Kuo, K. S. Dhir, Heuristic algorithms for the maximum diversity problem, Journal of Information and Optimization Sciences, 19(1) (1998), 109-132.
[18] F. Gortázar, R. Carrasco, A. P. Trinh, M. Gallego, A. Duarte, VNS variants for the max-mean dispersion problem, Electronic Notes in Discrete Mathematics, 47 (2015), 253-260.
[19] X. Gu, S. Zhao, Y. Wang, Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem, Discrete Optimization, (2021), page 100625.
[20] M. Inuiguchi, J. Ramık, Possibilistic linear programming: A brief review of fuzzy mathematical programming and a comparison with stochastic programming in portfolio selection problem, Fuzzy Sets and Systems, 111(1) (2000), 3-28.
[21] S. Kikuchi, P. Chakroborty, Place of possibility theory in transportation analysis, Transportation Research Part B: Methodological, 40(8) (2006), 595-615.
[22] H. Kumar, Some recent defuzzification methods, In Theoretical and Practical Advancements for Fuzzy System Integration, (2017), 31-48.
[23] C. C. Kuo, F. Glover, K. S. Dhir, Analyzing and modeling the maximum diversity problem by zero-one programming, Decision Sciences, 24(6) (1993), 1171-1185.
[24] X. Lai, J. K. Hao, A tabu search based memetic algorithm for the max-mean dispersion problem, Computers and Operations Research, 72 (2016), 118-127.
[25] X. Lai, J. K. Hao, F. Glover, A study of two evolutionary/tabu search approaches for the generalized max-mean dispersion problem, Expert Systems with Applications, 139 (2020), 112856.
[26] B. Liu, K. Iwamura, Chance constrained programming with fuzzy parameters, Fuzzy Sets and Systems, 94(2) (1998), 227-237.
[27] R. Martí, M. Gallego, A. Duarte, A branch and bound algorithm for the maximum diversity problem, European Journal of Operational Research, 200(1) (2010), 36-44.
[28] R. Martí, M. Gallego, A. Duarte, E. G. Pardo, Heuristics and metaheuristics for the maximum diversity problem, Journal of Heuristics, 19(4) (2013), 591-615.
[29] R. Martí, F. Sandoya, GRASP and path relinking for the equitable dispersion problem, Computers and Operations Research, 40(12) (2013), 3091-3099.
[30] A. Martínez-Gavara, T. Corberán, R. Martí, Grasp and tabu search for the generalized dispersion problem, Expert Systems with Applications, 173 (2021), 114703.
[31] M. J. Naderi, M. S. Pishvaee, S. A. Torabi, Applications of fuzzy mathematical programming approaches in supply chain planning problems, In Fuzzy Logic in Its 50th Year, Springer, (2016), 369-402.
[32] D. Nijimbere, S. Zhao, X. Gu, M. O. Esangbedo, N. Dominique, Tabu search guided by reinforcement learning for the max-mean dispersion problem, Journal of Industrial and Management Optimization, (2020), 3223-3246.
[33] D. Nijimbere, S. Zhao, H. Liu, B. Peng, A. Zhang, A hybrid metaheuristic of integrating estimation of distribution algorithm with tabu search for the max-mean dispersion problem, Mathematical Problems in Engineering, 2019 (2019), 1-16.
[34] F. Parreńo, R. Alvarez-Valdés, R. Martí, Measuring diversity. A review and an empirical analysis, European Journal of Operational Research, 289(2) (2021), 515-532.
[35] O. A. Prokopyev, N. Kong, D. L. Martinez-Torres, The equitable dispersion problem, European Journal of Operational Research, 197(1) (2009), 59-67.
[36] S. Roychowdhury, W. Pedrycz, A survey of defuzzification strategies, International Journal of Intelligent Systems, 16(6) (2001), 679-695.
[37] M. Safi, H. Maleki, E. Zaeimazad, A note on the zimmermann method for solving fuzzy linear programming problems, Iranian Journal of Fuzzy Systems, 4(2) (2007), 31-45.
[38] G. Shafer, et al, A mathematical theory of evidence, Princeton University Press Princeton, 1, 1976.
[39] J. Song, Y. Wang, H. Wang, Q. Wu, A. P. Punnen, An effective multi-wave algorithm for solving the max-mean dispersion problem, Journal of Heuristics, 25(4-5) (2019), 731-752.
[40] A. Talon, C. Curt, Selection of appropriate defuzzification methods: Application to the assessment of damperformance, Expert Systems with Applications, 70 (2017), 160-174.
[41] X. Yang, Some properties for fuzzy chance constrained programming, Iranian Journal of Fuzzy Systems, 8(4) (2011), 1-8.
[42] L. A. Zadeh, Fuzzy sets, Information and Control, 8(3) (1965), 338-353.
[43] L. A. Zadeh, Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems, 100 (1999), 9-34.
[44] H. J. Zimmermann, Fuzzy set theory and its applications, Kluwer Academic Publishers, 4 Edition, 2001.
Iranian Journal of Fuzzy Systems
Volume 19, Issue 5
September and October 2022
Pages 1-15

Files

Share

How to cite

Statistics