  Most optimization problems in applied sciences realistically involve
uncertainty in the parameters defining the cost function, of which only
statistical information is known beforehand. In a recent work we introduced a
message passing algorithm based on the cavity method of statistical physics to
solve the two-stage matching problem with independently distributed stochastic
parameters. In this paper we provide an in-depth explanation of the general
method and caveats, show the details of the derivation and resulting algorithm
for the matching problem and apply it to a stochastic version of the
independent set problem, which is a computationally hard and relevant problem
in communication networks. We compare the results with some greedy algorithms
and briefly discuss the extension to more complicated stochastic multi-stage
problems.
