Stochastic Matching Problem

The matching problem plays a basic role in combinatorial optimization and in statistical mechanics. In its stochastic variants, optimization decisions have to be taken given only some probabilistic information about the instance. While the deterministic case can be solved in polynomial time, stochastic variants are worst-case intractable. We propose an efficient method to solve stochastic matching problems which combines some features of the survey propagation equations and of the cavity method. We test it on random bipartite graphs, for which we analyze the phase diagram and compare the results with exact bounds. Our approach is shown numerically to be effective on the full range of parameters, and to outperform state-of-the-art methods. Finally we discuss how the method can be generalized to other problems of optimization under uncertainty.

Figure 1

Average energy density vs average connectivity of $L$ nodes. The four lines correspond (from top to bottom) to a greedy algorithm (assign ${\mathbf{x}}_1$ as if $\mathbf{t}=0$), to a “smart” greedy algorithm (find the maximum-weight matching on the full instance with weights on the nodes equal to their probability to be available and assign ${\mathbf{x}}_1$ accordingly), to the SP-derived algorithm (with $\mathbf{h}$ and $\mathbf{u}$ with support on $\{-1,1\}$), and to the offline lower bound of the optimum (with prior knowledge of $\mathbf{t}$). The vertical line is at $c=e$. Each point is an average of 50 to 100 instances, with error bars smaller than the point sizes. The instances have $|L_1|=1000$ and $|L_2|=|R|=2000$, with $p_l$ distributed uniformly in $]0,1]$.

Figure 2

Each point represents an instance with $|L_2|=|R|=2|L_1|$ and $p_l$ distributed uniformly in $]0,1]$. Top left: Energy vs number of samples $\rho$ obtained by CPLEX for $c=2.5$ and $|L_1|=1000$, compared with the one computed by the SP-derived algorithm. The energies and error bars were computed by resampling over $10000$ samples. Bottom left: CPLEX time (seconds) vs number of samples in the same instances. Top right: CPLEX time as a function of $|L_1|$ for several values of $c$ and $\rho =10$. Bottom right: Best fit of CPLEX times in bottom left with $f(x)=b{x}^a$ gives $a\simeq 2.35$.