odow / SDDP.jl

A JuMP extension for Stochastic Dual Dynamic Programming
https://sddp.dev
Other
309 stars 61 forks source link

Add code from biobjective paper #461

Closed odow closed 3 years ago

odow commented 3 years ago

We once wrote a paper on biobjective SDDP. So I don't forget where it is, the code is here: https://github.com/odow/biobjective_paper (private link, you'll get a 404 error until I make it public).

The code can be added to the /examples directory, but it depends quite heavily on some internal Gurobi functions, so it likely won't be added to the code proper.

The alternative is just to hack the trade-off weights using an objective state ala: https://odow.github.io/SDDP.jl/stable/examples/biobjective_hydro/

odow commented 3 years ago

It should also be trivial to add NISE: https://github.com/odow/MOO.jl/blob/master/src/algorithms/nise.jl This would allow us to use something other than Gurobi, and it would likely be more numerically stable at the expense of performance.

We'd want to support the API

pareto_weights = SDDP.train_biobjective(
    model; 
    nise_maximum_unique_policies::Int,  # Terminate once this many policies found (unless proven sooner)
    kwargs...,
)
SDDP.set_tradeoff_weight(model, weight)

For simplicity we'd probably disallow objective states + biobjective problems until there was demand.

odow commented 3 years ago

462 implements a very naive approach. There are two better alternatives:

  1. Run a simulation to get an estimate for the mean in objective space. Then use that to pick the new weight.
  2. Do the naive bracketing of 0.5 * (a + b), but sort the queue based on the expected improvement to the objective, i.e., solutions[w] - 0.5 * (solutions[a] + solutions[b]). If the improvement was large, it likely means that there is more to gain by searching the brackets each side.