Stochastic minimum weight vertex cover problem

Vertex cover problem is not only a famous problem in graph theory, but also a problem employed to model many real-life situations. In this paper, the minimum weight vertex cover problem with stochastic weights is studied. We propose for the first time the concepts of expected minimum weight vertex cover, alpha-minimum weight vertex cover and the most minimum weight vertex cover. According to different decision criteria, three types of models: expected value model, chance-constrained programming and dependent-chance programming are formulated. We produce a hybrid intelligent algorithm integrating stochastic simulation and genetic algorithm to solve the models. Finally, a numerical example is given to illustrate the effectiveness of the algorithm.