# Speeding up multilinear PRA branch-and-bound algorithm with worst-case exponential time scenario with respect to basic events

The algorithm is a branch-and-bound algorithm that calculates dominances for PRA, probalistic risk assessment. The task was to find faster ways to do it in numerical software such as Matlab but we found it extremely hard, more here. Now I am trying to find ways to speed it up in symbolic softwares such as Mathematica.

The algorithm uses multilinearity but not with respect to constant term. The worst case time scenario with respect to basic events is exponential. This does not mean that it is exponential with respect to minimal cut sets. It is a method to analyse the impact of epistemic uncertainty about event probabilities in fault tree analysis. The algo is based on a theorem in multilinear optimization according to which the extreme values of multilinear function $f: HR \rightarrow \mathbb R$ are attained at the vertices of HR where HR is a hyperrectangle in $\mathbb R^n$. Basically the idea of this algo is to traverse the corners in the hyperrectangle. So:

what kind of methods would you use to speed up this kind of recursive algorithm?

Algorithm

Algo[f0_, lb0_, ub0_] :=
Module[{f = f0, lb = lb0, ub = ub0, monomials, fp, fm, bvar, blb,
bub}, If[f == 0 || f == 0.0, Return[True]];
monomials = f // MonomialList;
fp = Select[monomials*1.0*D, (First[#] >= 0) &] /. {D -> 1};
fm = Select[monomials*1.0*D, (First[#] < 0) &] /. {D -> 1};
If[Plus @@ (fp /. lb) + Plus @@ (fm /. ub) >= 0, Return[True]];
If[Plus @@ (fp /. ub) + Plus @@ (fm /. lb) < 0, Return[False]];
bvar = Variables[f] // First;
blb = Select[lb, ((# // First) == bvar) &];
bub = Select[ub, ((# // First) == bvar) &];
Algo[(f /. blb), lb, ub] \[And] Algo[(f /. bub), lb, ub]];


Example how to use this function

Algo[Subscript[p, 1] + Subscript[p, 2] - Subscript[p, 1] Subscript[p, 2],
Table[Subscript[p, i] -> 0.01, {i, 7}], Table[Subscript[p, i] -> 0.04, {i, 7}]]

-
It would help if you give some example where the function is noticably slow (perhaps a larger one than the one you gave). –  Leonid Shifrin Apr 9 '13 at 20:49