Finding the weighted stable set of a graph with uncertain weights

Document Type : Research Paper

Author

Department of Mathematics, Faculty of Basic Sciences, Maragheh University, Maragheh, Iran

Abstract

The inherent characteristics of real-world data is uncertainty. If data is generated in valid experiments or collected standard, probability theory or fuzzy theory is a powerful tool for analysis it in the uncertainty conditions. But data is not always reliable; especially when it is not possible to perform multiple tests or reliable data collection. In this context, referring to the beliefs of experts in the field in question is an alternative approach and uncertainty theory is a tool by which the beliefs of experts can be mathematically incorporated into the problem-solving structure. A stable set has a wide range of applications in many fields, while in most cases its problems are without reliable data. In this paper, we investigate the finding of stable weighted sets with uncertain weights. These weights have an uncertain distribution based on the degree of belief of the field expert. For this purpose, we offer two methods. In the first method, by introducing the concept of chance constraint, we come to an integer linear programming model with definite coefficients. The second method is based on the concept of uncertain expected value. Finally, a numerical example for these two methods is presented.

Keywords

References

[1] I. M. Bomze , M. Budinich, P. M. Pardalos and M. Pelillo, The maximum clique problem, Handbook of combi-natorial optimization, Supplement, Kluwer Acad. Publ., Dordrecht, A (1999) 1–74.
 [2] S. Burer, R. D. C. Monteiro and Y. Zhang, Maximum stable set formulations and heuristics based on continuous optimization, Math. Program., 94 (2002) 137–166.
[3] L. Chen, J. Peng, B. Zhang and S. Li, Uncertain programming model for uncertain minimum weight vertex covering problem, J. Intell. Manuf., 28 2017 625-632.
[4] M. Djahangiri and A. Ghaffari-Hadigheh, Uncertain weighted dominating set: a prototype application on natural disaster relief management, Soft Comput., 22 (2018) 1003–1012.
[5] Y. Gao, Shortest path problem with uncertain arc lengths,Comput. Math. Appl., 62 (2011) 2591–2600.
[6] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, Calif., 1979.
[7] A. Ghaffari-Hadigheh, Roman domination problem with uncertain positioning and deployment costs, Soft Com-put., 24 (2020) 2637-2645.
[8] Sh. Han, Z. Peng and S. Wang, The maximum flow problem of uncertain network, Inform. Sci., 265 (2014) 167–175.
[9] B. Liu and Y. K. Liuand, Expected value of fuzzy variable and fuzzy expected value models, IEEE Trans. Fuzzy Syst., 10 (2002) 445–450.
[10] B. Liu, Uncertainty theory, Second edition. Studies in Fuzziness and Soft Computing, 154, Springer, Berlin, 2007.
[11] B. Liu, Some research problems in uncertainty theory, J. Uncertain Syst., 3 (2009) 3–10.
[12] B. Liu, Uncertain risk analysis and uncertain reliability analysis, J. Uncertain Syst., 4 (2010) 163–170.
[13] B. Liu, Toward uncertain finance theory, J. Uncertain. Anal. Appl., 1 (2013) 1–5.
[14] B. Liu, Uncertainty theory, 24, Springer, Berlin, 2015.
[15] E. Maslov, M. Batsyn and P. M. Pardalos, Speeding up branch and bound algorithms for solving the maximum clique problem, J. Global Optim., 59 (2014) 1–21.
[16] S. Rebennack, M. Oswald, D. O. Theis, H. Seitz, G. Reinelt and P. M. Pardalos, A branch and cut solver for the maximum stable set problem, J. Comb. Optim., 21 (2011) 434–457.
[17] F. Rossi and S. Smriglio, A branch-and-cut algorithm for the maximum cardinality stable set problem, Oper. Res. Lett., 28(2) (2001) 63–74.
[18] P. San Segundo, D. Rodríguez-Losada and A. Jiménez, An exact bit-parallel algorithm for the maximum clique problem, Comput. Oper. Res., 38 (2011) 571–581.
[19] E. Tomita and T. Kameda, An efficient branch-and-bound algorithm for finding a maximum clique with com-putational experiments, J. Global Optim., 37 (2007) 95–111.
[20] Y. Zhu, Uncertain optimal control with application to a portfolio selection model, Cybern. Syst. Int. J., 41 (2010) 535–547.

Files

History

  • Receive Date: 08 March 2022
  • Revise Date: 01 August 2022
  • Accept Date: 22 August 2022
  • Publish Date: 22 May 2022

Share

How to cite

Statistics