Uncertain Measure and its Application in Minimum Weighted Maximal Matching Problem

The inherent feature of real-world data is uncertainty. If data is generated in valid experiments or standard collections, probability theory or fuzzy theory is a powerful tool for analyzing them. But data is not always reliable, especially when it is not possible to perform a reliable test or data collection multiple times. In this situations, 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. In this paper, we investigate the finding minimum weighted maximal matching with uncertain weights. For this purpose, we offer two methods. In the first method, by introducing the concept of chance constraint, we obtain 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:

Uncertainty theory , Graph , Maximal matching , integer programming