Optimization under uncertainty deals with the problem of finding the minimum of a cost function which depends on some stochastic parameters, given some partial information about their value (e.g. their probability distribution). We consider a variant of the assignment problem in which part of the optimization decisions have to be taken with only partial (probabilistic) knowledge of the instance, and propose a solution method which combines some features of Survey Propagation and of Belief Propagation, and which is capable of solving large scale instances of such problems (provided they can be treated with the cavity method in the deterministic setting).