search

odow / SDDP.jl

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

SDDP.Asynchronous for MSPFormat #650

Closed bonnkleiford closed 1 year ago

bonnkleiford commented 1 year ago

Hi Oscar,

How are you? I hope everything is well.

I am exploring the SDDP.Asynchronous feature of SDDPjl for the benchmarking. I tried to follow the documentation as much as I can but I got this error message:

You must supply an optimizer for the policy graph, either by passing
one to the `optimizer` keyword argument to `PolicyGraph`, or by
using `JuMP.set_optimizer(model, optimizer)`.

Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:35
 [2] _initialize_solver(node::SDDP.Node{String}; throw_error::Bool)
   @ SDDP ~/.julia/1.8/packages/SDDP/1uYYz/src/algorithm.jl:317
 [3] _initialize_solver(model::SDDP.PolicyGraph{String}; throw_error::Bool)
   @ SDDP ~/.julia/1.8/packages/SDDP/1uYYz/src/algorithm.jl:343
 [4] master_loop(async::SDDP.Asynchronous, model::SDDP.PolicyGraph{String}, options::SDDP.Options{String})
   @ SDDP ~/.julia/1.8/packages/SDDP/1uYYz/src/plugins/parallel_schemes.jl:238
 [5] train(model::SDDP.PolicyGraph{String}; iteration_limit::Nothing, time_limit::Int64, print_level::Int64, log_file::String, log_frequency::Int64, log_every_seconds::Float64, run_numerical_stability_report::Bool, stopping_rules::Vector{SDDP.AbstractStoppingRule}, risk_measure::SDDP.Expectation, sampling_scheme::SDDP.InSampleMonteCarlo, cut_type::SDDP.CutType, cycle_discretization_delta::Float64, refine_at_similar_nodes::Bool, cut_deletion_minimum::Int64, backward_sampling_scheme::SDDP.CompleteSampler, dashboard::Bool, parallel_scheme::SDDP.Asynchronous, forward_pass::SDDP.DefaultForwardPass, forward_pass_resampling_probability::Nothing, add_to_existing_cuts::Bool, duality_handler::SDDP.ContinuousConicDuality, forward_pass_callback::SDDP.var"#97#104", post_iteration_callback::SDDP.var"#98#105")
   @ SDDP ~/.julia/1.8/packages/SDDP/1uYYz/src/algorithm.jl:1100
 [6] top-level scope
   @ In[10]:1

This is what I did so far:

using SDDP, GLPK, Gurobi, DataFrames, CSV, Plots, HiGHS, NBInclude
using Distributed
Distributed.addprocs(5);

model = SDDP.MSPFormat.read_from_file("(01_7)_100")
SDDP.set_optimizer(model, Gurobi.Optimizer)

SDDP.train(model, time_limit = 10, print_level=1, log_frequency=1,
    # parallel_scheme = SDDP.Asynchronous())

I have here the json files for reproduction.

(01_7)_100.zip

Best,

odow commented 1 year ago

I cannot open the file because I don't have enough memory on my laptop:

julia> model = SDDP.MSPFormat.read_from_file("/tmp/(01_7)_100/(01_7)_100")
A policy graph with 2500 nodes.
 Node indices: 1766, ..., 306

julia> SDDP.set_optimizer(model, Gurobi.Optimizer)
ERROR: Gurobi Error 10001:

You probably need: https://odow.github.io/SDDP.jl/stable/guides/improve_computational_performance/#Initialization-hooks

SDDP.set_optimizer(model, Gurobi.Optimizer)
SDDP.train(
    model;
    parallel_scheme = SDDP.Asynchronous() do m::SDDP.PolicyGraph
        env = Gurobi.Env()
        JuMP.set_optimizer(m, () -> Gurobi.Optimizer(env))
    end,
)

But a much bigger problem is that SDDP.jl is not designed for lattices with 2500 nodes because it creates a separate JuMP model for each node in the lattice. I think I need to identify stagewise independent structure in the lattice.json and build that instead.

The asynchronous performance is probably also bad because of https://github.com/odow/SDDP.jl/issues/599. For this problem you'll end up creating 2500 * 5 = 12,500 different Gurobi models...

odow commented 1 year ago

This uses #653 which is very important to ensure that only 25 subproblems get built instead of 2500.

The for-loop is a temporary fix for #654.

(base) oscar@Oscars-MBP /tmp % julia --project=sddp
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.7 (2022-07-19)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> using Distributed

julia> Distributed.addprocs(5);

julia> @everywhere begin
           import Pkg
           Pkg.activate("/tmp/sddp")
       end
  Activating environment at `/tmp/sddp/Project.toml`
      From worker 4:      Activating environment at `/tmp/sddp/Project.toml`
      From worker 3:      Activating environment at `/tmp/sddp/Project.toml`
      From worker 2:      Activating environment at `/tmp/sddp/Project.toml`
      From worker 6:      Activating environment at `/tmp/sddp/Project.toml`
      From worker 5:      Activating environment at `/tmp/sddp/Project.toml`

julia> @everywhere begin
           using SDDP, Gurobi
       end

julia> model = SDDP.MSPFormat.read_from_file("/tmp/(01_7)_100/(01_7)_100")
A policy graph with 25 nodes.
 Node indices: 24, ..., 3

julia> SDDP.set_optimizer(model, Gurobi.Optimizer)

julia> for node in values(model.nodes)
           node.optimizer = Gurobi.Optimizer
       end

julia> SDDP.train(
           model;
           iteration_limit = 10,
           log_every_seconds = 0.0,
           parallel_scheme = SDDP.Asynchronous(; use_master = false) do m::SDDP.PolicyGraph
               env = Gurobi.Env()
               SDDP.set_optimizer(model, () -> Gurobi.Optimizer(env))
           end,
       )
-------------------------------------------------------------------
         SDDP.jl (c) Oscar Dowson and contributors, 2017-23
-------------------------------------------------------------------
problem
  nodes           : 25
  state variables : 1
  scenarios       : 1.00000e+50
  existing cuts   : false
options
  solver          : Asynchronous mode with 5 workers.
  risk measure    : SDDP.Expectation()
  sampling scheme : SDDP.InSampleMonteCarlo
subproblem structure
  VariableRef                             : [6, 6]
  AffExpr in MOI.EqualTo{Float64}         : [2, 2]
  VariableRef in MOI.GreaterThan{Float64} : [5, 5]
  VariableRef in MOI.LessThan{Float64}    : [1, 2]
numerical stability report
  matrix range     [1e+00, 1e+00]
  objective range  [1e+00, 9e+01]
  bounds range     [2e+02, 1e+06]
  rhs range        [6e+01, 2e+02]
-------------------------------------------------------------------
 iteration    simulation      bound        time (s)     solves  pid
-------------------------------------------------------------------
         1   1.200143e+05  9.434539e+04  5.044423e+01       100   2
         2   1.346048e+05  9.434539e+04  5.202458e+01      2700   5
         3   1.262865e+05  9.434539e+04  5.213052e+01      2800   6
         4   1.280591e+05  9.434539e+04  5.214389e+01      2900   3
         5   1.309676e+05  9.434539e+04  5.215937e+01      3000   4
         6   1.179271e+05  9.906205e+04  5.217376e+01      3100   2
         7   1.029976e+05  1.019992e+05  5.218820e+01      3200   2
         8   1.140694e+05  1.022385e+05  5.220257e+01      3300   2
         9   1.132411e+05  1.022385e+05  5.221371e+01      3400   4
        10   1.006086e+05  1.025582e+05  5.222394e+01      3500   2
-------------------------------------------------------------------
status         : iteration_limit
total time (s) : 5.222394e+01
total solves   : 3500
best bound     :  1.025582e+05
simulation ci  :  1.188776e+05 ± 7.084132e+03
numeric issues : 0
-------------------------------------------------------------------

The 50 second start up latency is weird. But I don't have the time to look into it. I don't expect the asynchronous implementation to perform well in your benchmarks. See #599.

odow commented 1 year ago

Should be fixed if you use ] add SDDP#master

odow commented 1 year ago

Should be fixed by v1.6.2

bonnkleiford commented 1 year ago

Oh, wow!

Thanks a lot! I will try it out.

On Thu, Aug 24, 2023 at 9:57 AM Oscar Dowson @.***> wrote:

Should be fixed by v1.6.2

— Reply to this email directly, view it on GitHub https://github.com/odow/SDDP.jl/issues/650#issuecomment-1691195209, or unsubscribe https://github.com/notifications/unsubscribe-auth/AJAVHMST7TN6FZOIQISCOQLXW4CPLANCNFSM6AAAAAA33QKF5Y . You are receiving this because you authored the thread.Message ID: @.***>

odow commented 1 year ago

Is the library open-source yet? Without a formal spec or a bunch of examples, it's quite hard to know if I've implemented things correctly.

bonnkleiford commented 1 year ago

No, not yet. Been busy with thesis submission. I can give you access to the data for sure, if you want to test it out.

On Fri, Aug 25, 2023 at 1:39 AM Oscar Dowson @.***> wrote:

Is the library open-source yet? Without a formal spec or a bunch of examples, it's quite hard to know if I've implemented things correctly.

— Reply to this email directly, view it on GitHub https://github.com/odow/SDDP.jl/issues/650#issuecomment-1692549434, or unsubscribe https://github.com/notifications/unsubscribe-auth/AJAVHMTWA63GCYBQBZFGTVTXW7Q3BANCNFSM6AAAAAA33QKF5Y . You are receiving this because you authored the thread.Message ID: @.***>

odow commented 1 year ago

Why does the library need to stay private until you've written the paper/submitted a thesis? It'd be easier to iterate and fix any problems if it was open. It doesn't need to be in a perfect state to begin with.

bonnkleiford commented 1 year ago

Good point. Although, I was also rooting to include some initial bechmarking results (that I would include in my thesis). But yeah, I’ll ask for a greenlight and let you know.

On Sat, Aug 26, 2023 at 12:23 AM Oscar Dowson @.***> wrote:

Why does the library need to stay private until you've written the paper/submitted a thesis? It'd be easier to iterate and fix any problems if it was open. It doesn't need to be in a perfect state to begin with.

— Reply to this email directly, view it on GitHub https://github.com/odow/SDDP.jl/issues/650#issuecomment-1693992918, or unsubscribe https://github.com/notifications/unsubscribe-auth/AJAVHMVXAG6CHTA2NI6KGTDXXEQXJANCNFSM6AAAAAA33QKF5Y . You are receiving this because you authored the thread.Message ID: @.***>

odow commented 1 year ago

Any update? If not, I will close this issue.

bonnkleiford commented 1 year ago

Hi Oscar,

Thanks again for the help on this. I checked and the Asynchronous method works. I am still finishing up the benchmarking for MSPPy and SDDP.jl should be next.

Anyway, I have publicly made MSPLib available. Only the initial version, of course, with the MSPFormat Files of the Synthetic Problems (levels of difficulty in the Problem Instance Charts). --> https://github.com/bonnkleiford/MSPLib-Library/

Thanks again for your help!

On Thu, Aug 31, 2023 at 12:17 AM Oscar Dowson @.***> wrote:

Any update? If not, I will close this issue.

— Reply to this email directly, view it on GitHub https://github.com/odow/SDDP.jl/issues/650#issuecomment-1699925356, or unsubscribe https://github.com/notifications/unsubscribe-auth/AJAVHMWAZ4JYU2E3QROLB3LXX63YVANCNFSM6AAAAAA33QKF5Y . You are receiving this because you authored the thread.Message ID: @.***>

-- With much respect,

Bonn Kleiford D. Seranilla, MOST PhD in Operations and Supply Chain Management Luxembourg Center for Logistics and Supply Chain Management University of Luxembourg @. @.> @.***

odow commented 1 year ago

Closing for now. I opened a few issues at https://github.com/bonnkleiford/MSPLib-Library, so let's chat there.