Chance constrained bottleneck spanning tree problem

Chance constrained bottleneck spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor19952265
Country: Switzerland
Volume: 56
Issue: 1
Start Page Number: 177
End Page Number: 187
Publication Date: Jun 1995
Journal: Annals of Operations Research
Authors: ,
Keywords: programming: probabilistic
Abstract:

In this paper the authors consider a stochastic version of the bottleneck spanning tree in which edge costs are independent random variables. The present problem is to find an optimal spanning tree and optimal satisficing level of the chance constraint with respect to the bottleneck (maximum cost) edge of the spanning tree. The problem is first transformed into a deterministic equivalent problem. Then a subproblem in order to solve the problem is introduced and the close relation between these problems is clarified. Finally, based on the relation, polynomial time solution procedures to solve the problem are proposed under two special functions of satisficing level which are given as examples to be solved easily.

Reviews

Required fields are marked *. Your email address will not be published.