Git Product home page Git Product logo

sddip.jl's People

Stargazers

avatar avatar avatar avatar avatar avatar avatar avatar

Watchers

avatar avatar avatar avatar avatar

Forkers

bfpc chrisfuelor znwing

sddip.jl's Issues

The methods are really slow

I tried @EyobZewdie's booking management problem with 6 days, 4 rooms (i.e. 24 states), and 10 stages on my workstation (running in parallel with 4 core), and after 12 hours it had only done 1000 iterations with the subgradient method and the bound hadn't moved from the intial bound. The level method did slightly better (535 iterations, and the bound dropped slightly).

It seems the current implementation just can't handle these problem sizes. Any idea's on how to speed up the solves? Or different methods for the lagrangian solver?

Move out Lagrangian.jl part

The part of the library that solves the Lagrangian dual could be stand-alone and could be made more generic, perhaps for other cut types too.

f_approx not defined

When you run the level method and it hits the maximum number of iterations it fails with f_approx not defined.

Adding complicating constraints

In the Lagrangian part of SDDiP.jl:
Having to specify a relaxed RHS for complicating constraints is ugly.
It would be nicer if complicating constraints never got added or if we had better defaults for RHSs.

Tests failing on Travis

Air conditioning, vehicle location, and generation expansion examples hit numeric issues with GLPK 4.61. I don't see the same issues with GLPK 4.52.

solutions

Is there any way to retrive the solution results by var-stage-node?
Br,
CV

Status of SDDiP

Todos

  • Different cut types are a WIP
  • Maybe pi-s should be cached for each stage problem to start solves
  • Generation expansion example breaks with GLPK 4.61

Subgradient gets a NaN somewhere

https://gist.github.com/odow/61c0585bfb91d59577c8a6ce8c2f9a83

D:\SDDiP>D:/julia/julia-0.6/bin/julia booking_management.jl
-------------------------------------------------------------------------------
                      SDDP Solver. © Oscar Dowson, 2017.
-------------------------------------------------------------------------------
    Solver:
        Serial solver
    Model:
        Stages:         5
        States:         6
        Subproblems:    5
        Value Function: Default
-------------------------------------------------------------------------------
              Objective              |  Cut  Passes    Simulations   Total
     Simulation       Bound   % Gap  |   #     Time     #    Time    Time
-------------------------------------------------------------------------------
        7.000         47.500         |     1    1.7      0    0.0    1.7

 ... lines omitted ...

       19.000         40.736         |    30    8.5      0    0.0    8.6
       17.000         39.653         |    31    8.8      0    0.0    8.9
ERROR: LoadError: Invalid coefficient NaN on variable vacancy_before_decision[1,
1]
Stacktrace:
 [1] assert_isfinite(::JuMP.GenericAffExpr{Float64,JuMP.Variable}) at C:\Users\o
dow003\.julia\v0.6\JuMP\src\affexpr.jl:95
 [2] prepAffObjective(::JuMP.Model) at C:\Users\odow003\.julia\v0.6\JuMP\src\sol
vers.jl:500
 [3] #build#119(::Bool, ::Bool, ::JuMP.ProblemTraits, ::Function, ::JuMP.Model)
at C:\Users\odow003\.julia\v0.6\JuMP\src\solvers.jl:327
 [4] (::JuMP.#kw##build)(::Array{Any,1}, ::JuMP.#build, ::JuMP.Model) at .\<miss
ing>:0
 [5] #solve#116(::Bool, ::Bool, ::Bool, ::Array{Any,1}, ::Function, ::JuMP.Model
) at C:\Users\odow003\.julia\v0.6\JuMP\src\solvers.jl:168
 [6] (::JuMP.#kw##solve)(::Array{Any,1}, ::JuMP.#solve, ::JuMP.Model) at .\<miss
ing>:0
 [7] solve_primal(::JuMP.Model, ::SDDiP.Lagrangian.LinearProgramData{SDDiP.Lagra
ngian.SubgradientMethod{SDDiP.Lagrangian.Unit},SDDiP.Lagrangian.LinearProgram},
::Array{Float64,1}) at C:\Users\odow003\.julia\v0.6\SDDiP\src\Lagrangian\utils.j
l:87
 [8] lagrangian_method!(::SDDiP.Lagrangian.LinearProgramData{SDDiP.Lagrangian.Su
bgradientMethod{SDDiP.Lagrangian.Unit},SDDiP.Lagrangian.LinearProgram}, ::JuMP.M
odel, ::Array{Float64,1}) at C:\Users\odow003\.julia\v0.6\SDDiP\src\Lagrangian\s
ubgradient.jl:90
 [9] lagrangiansolve!(::SDDiP.Lagrangian.LinearProgramData{SDDiP.Lagrangian.Subg
radientMethod{SDDiP.Lagrangian.Unit},SDDiP.Lagrangian.LinearProgram}, ::JuMP.Mod
el, ::Array{Float64,1}) at C:\Users\odow003\.julia\v0.6\SDDiP\src\Lagrangian\Lag
rangian.jl:115
 [10] #SDDiPsolve!#2(::Bool, ::Int64, ::Array{Any,1}, ::Function, ::JuMP.Model)
at C:\Users\odow003\.julia\v0.6\SDDiP\src\solver.jl:87
 [11] (::SDDiP.#kw##SDDiPsolve!)(::Array{Any,1}, ::SDDiP.#SDDiPsolve!, ::JuMP.Mo
del) at .\<missing>:0
 [12] #solve#116(::Bool, ::Bool, ::Bool, ::Array{Any,1}, ::Function, ::JuMP.Mode
l) at C:\Users\odow003\.julia\v0.6\JuMP\src\solvers.jl:151
 [13] (::JuMP.#kw##solve)(::Array{Any,1}, ::JuMP.#solve, ::JuMP.Model) at .\<mis
sing>:0
 [14] JuMPsolve(::Type{SDDP.BackwardPass}, ::SDDP.SDDPModel{SDDP.DefaultValueFun
ction{SDDP.DefaultCutOracle}}, ::JuMP.Model) at C:\Users\odow003\.julia\v0.6\SDD
iP\src\solver.jl:8
 [15] solvesubproblem!(::Type{SDDP.BackwardPass}, ::SDDP.SDDPModel{SDDP.DefaultV
alueFunction{SDDP.DefaultCutOracle}}, ::JuMP.Model, ::Float64) at C:\Users\odow0
03\.julia\v0.6\SDDP\src\valuefunctions.jl:115
 [16] backwardpass!(::SDDP.SDDPModel{SDDP.DefaultValueFunction{SDDP.DefaultCutOr
acle}}, ::SDDP.Settings, ::Bool) at C:\Users\odow003\.julia\v0.6\SDDP\src\SDDP.j
l:259
 [17] iteration!(::SDDP.SDDPModel{SDDP.DefaultValueFunction{SDDP.DefaultCutOracl
e}}, ::SDDP.Settings, ::Bool) at C:\Users\odow003\.julia\v0.6\SDDP\src\SDDP.jl:2
83
 [18] solve(::SDDP.Serial, ::SDDP.SDDPModel{SDDP.DefaultValueFunction{SDDP.Defau
ltCutOracle}}, ::SDDP.Settings) at C:\Users\odow003\.julia\v0.6\SDDP\src\SDDP.jl
:320
 [19] #solve#42(::Int64, ::Float64, ::SDDP.MonteCarloSimulation, ::SDDP.BoundCon
vergence, ::Int64, ::Int64, ::String, ::SDDP.Serial, ::Bool, ::String, ::JuMP.#s
olve, ::SDDP.SDDPModel{SDDP.DefaultValueFunction{SDDP.DefaultCutOracle}}) at C:\
Users\odow003\.julia\v0.6\SDDP\src\SDDP.jl:503
 [20] (::JuMP.#kw##solve)(::Array{Any,1}, ::JuMP.#solve, ::SDDP.SDDPModel{SDDP.D
efaultValueFunction{SDDP.DefaultCutOracle}}) at .\<missing>:0
 [21] include_from_node1(::String) at .\loading.jl:569
 [22] include(::String) at .\sysimg.jl:14
 [23] process_options(::Base.JLOptions) at .\client.jl:305
 [24] _start() at .\client.jl:371
while loading D:\SDDiP\booking_management.jl, in expression starting on line 96

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.