Kokako to-do list

[odow]

Features

• [x] Add a test function that accepts a sampling scheme. Defaults to in-sample Monte Carlo.
  • I've called this simulate. There is an interesting idea for a train-validation-test stopping rule: train the policy and every so often simulate that policy on a validation dataset. Stop once the policy fails to improve on the validation dataset. Discussion in #3.
• Stopping rules
  • [x] Bound stalling
  • [x] Statistical (#6)
  • [ ] HdM variant of statistical
  • [x] Time limit
  • [x] Iteration limit
• Sampling schemes:
  • Monte Carlo Infinite horizon
  • [x] terminate at a dummy leaf
  • [x] terminate at a cycle, store the state, and unwind
  • [x] Historical
  • [ ] Risk-adjusted (forward pass)
  • [x] OutOfSampleMonteCarlo
• Implement iteration schemes:
  • SDDP (N forward, N backward)
  • scenario incrementation (1, 2, ..., N forward)
  • CUPPS
  • Dynamic sequencing protocol https://d-nb.info/1046905090/34 (Wolf's thesis actually has a lot of great stuff aimed at L-shaped nested Benders) (Covered by #116)
• [x] @state macro` I had a lot of issues with this. There seems to be some local scoping/macro hygiene issue passing local variables in Kokako scope through to JuMP. Related issues: https://github.com/JuliaOpt/JuMP.jl/pull/1497, https://github.com/JuliaOpt/JuMP.jl/pull/1517 I went the JuMPExtension route. I owe Benoit big-time.
  • [x] average cost method of Foster. See https://github.com/odow/SDDP.jl/pull/179
  • [x] price interpolation

Performance improvements

• Implement cut selection and cut oracles.
  • [x] LevelOne (#8)
• [x] Only add the cut if it improves by more than some ϵ
• [x] Add cuts to other nodes in graph with same children
  • We can pre-process the initial graph object to obtain the list. Instead of just nodes with identical children, we could also add on a subset of the children. It also needs a train option to enable/disable.
• [ ] Be smarter about adding cuts to other nodes in the graph. We could detect that we've solved the majority of subproblems and we only need to solve a few more to be able to add a cut. That's an improvement for complicated graphs though.
• Numerical stability improvements:
  • [x] Project state variables to their bounds on forward pass.
  • Analyze coefficients for user-warning. Things to check
  • [x] Large coefficients > 1e7 log10(maximum(abs.(coefficients))) > 7
  • [x] Small coefficients < 1e-2 -6 < log10(minimum(abs.(coefficients))) < -2
  • [x] High dynamic range log10(maximum(abs.(coefficients)) - minimum(abs.(coefficients))) > 8
  • [ ] Throw away cuts that are numerically almost identical.
  • [x] Parallelism
  • Regularization
  • [ ] Asamov & Powell's paper
  • [ ] Some level method http://www.inrialpes.fr/bipop/people/zaourar/docs/talk_roadef_2014.pdf
  • [ ] What about forcing the state iterates on the forward pass to be some minimum distance away from the previous iterate? Unlike 2-stage benders, we necessarily don't want our iterates to converge. We want to explore the state-space, or at the very least, add cuts that are not near to each other to prevent numerical issues.
  • [ ] Scenario reduction. See https://github.com/odow/Kokako.jl/pull/6#discussion_r243080031

Public facing

• [x] Port the examples from SDDP.jl
• Documentation.
  • [x] Hopefully we can just grab the SDDP.jl tutorials and modify them.
  • [x] We need a "Guide to transitioning from SDDP.jl"
• [x] Pretty the printing
• [x] Logging.
• [x] Plotting.

[odow]

Closing this since the big issues are done, and the few minor ones aren't a priority.

[Thuener]

@odow, I'm having some issues with high-dimension problems (with many states). Looking around, I found this issue here that you mention https://castle.princeton.edu/wp-content/uploads/2020/11/Asamov-Regularized-decomposition-of-high-dimensional-multistage-stochastic-programs-with-Markov-uncertainty.pdf.

Any updates on the Asamov & Powell's quadratic regularization implementation?

[odow]

Any updates on the Asamov & Powell's quadratic regularization implementation?

Nope. We could discuss off-line perhaps. I tend to think that regularization is dumb. It doesn't make sense to regularize to a previous sample path if the uncertainty is different. It only makes sense if the state variables have very low variance.

SDDP.jl is just not designed for high-dimensional problems.