New minmoney

[cliffckerr]

Totally new and vastly improved minimize money algorithm. Based on an MCMC-like process. It works as follows:

1. Check that infinite spending does meet the target and zero spending doesn't, and terminate if either is not the case (lines 1080-1130).
2. Find the scaled version of the current budget (call it b_current) that meets the target (note: there is a corner case here that if one or more critical programs starts with exactly zero funding, this step will fail...am not sure whether this is worth addressing). Call this new total budget amount b_scaled (lines 1250-1255).
3. Monte Carlo global search: create n (default: 50) random budget vectors of length b_scaled, and keep any that still meet the targets (i.e., are at least as good as the scaled version of the current budget) (lines 1257-1283).
4. Shrink the total budget until only one of these vectors still meets the target (lines 1285-1290).
5. Assign a proportion of the total budget (e.g. 30%) in the direction of this vector, and then repeat steps 3 and 4 to assign the remaining budget in stages (default: 30%, 60%, 80%, 90%, 100%).
6. Local refinement search: loop randomly over each program, and try reducing its budget by a given amount, and reassigning some proportion (default: 50%) of this budget to other programs (lines 1300-1350).

Graphically, you can think of the algorithm as follows: step 1 checks that a boundary exists between meeting and not meeting the targets. Step 2 figures out how far from the origin this boundary is in the direction of the current budget (answer: b_scaled). Step 3 creates a "spray" of vectors of length b_scaled in random directions from the origin. Step 4 shrinks the vector until only one remains, then step 5 steps partway along in this direction. Steps 3-5 are repeated with ever-smaller sprays of vectors, as more and more of the budget is assigned. Step 6 then takes small steps in each direction from this point, until every possible step that reduces the budget also crosses the boundary.

@robynstuart and @gchadder3 please review. This is considered a WIP; before merging, there are a couple things that need to be fixed:

• The plotting should be removed (or at least made optional)
• Ideally the hard-coded parameters would be made into kwargs (though this is hard to propagate through to optimize() and project.optimize())
• Sometimes the programs seem to go negative (usually -0.0, but still!)
• I'm not sure that the final results being output exactly match what the algorithm is computing (i.e. something may be going wrong in lines 1430-1444).

See also analyses/misc/minmoney-testing.py for the same thing in script form.

To test, you can just use e.g.

import optima as op
P = op.loadproj('Swaziland_20180523.prj')
#P = op.demo(0)
P.optimize(which='money')
op.pygui(P)

It takes about 5 minutes to run for the demo project and about 30 minutes to run for Swaziland (for example).

[cliffckerr]

@robynstuart there's more that could be done but this seems to work for now, we can test more with real-world examples, i imagine at least one fix-up PR will be required