Speeding up the non-negativity algorithm for multilinear function with interval probabilities?

Question

The algorithm is a branch-and-bound algorithm that calculates the non-negativity of a multilinear function with interval probabilities. The lines 9-11 has an optimization that is explained on the 10-14 lines of Table 1 in publication here.

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]];

Simple example: non-negativity check for $p_1+p_2-p_1p_2$ with bounds $p_i\in[0.01,0.04]$

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}]]

Answer 1

I wrote my thesis "Implementation of an algorithm for verifying the non-negativity of a multilinear function in a hypercube" about this here (password is "sal" and username "sal"). The key algorithm is not specified in the publication, focusing only on the key implementation idea with the hypercubes -- this was a requirement by my instructor.

Shortly

I showed that the nature of data (nature of the multilinear function) is an important decision variable in choosing the optimization! This is a fascinating concept -- it basically mean: you need to specify your multilinear function more specifically: whatever method you choose it needs to be specific, I like graph-theoretical/polytopical way of characterising the multilinear functions because then you are simply considering polytopical problems. You transform the earlier messy multilinear problem into a new domain where you can use their tools making it easy to deal with.

Optimization on the Lines 9-11

This optimization strategy (invented by my instructor) is not optimal with all kind of data. I showed this in my thesis by finding cases where they did not work, multilinear functions in Table 4 on the page 20. The way I found the multilinear functions is not specified and is an intriguing research topic because MLFs have many applications over different industries.

You can find more about the research here, not hard stuff or let say you need to be very careful :)