search

odow / SDDP.jl

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

Fix bug in lagrangian duality #457

Closed odow closed 3 years ago

odow commented 3 years ago

StrengthenedConicDuality can't use the higher bounds because the continuous dual solution is likely infeasible. If the bounds are too tight, then we'll get an incorrect dual objective value.

There must be something like adding a feasibility cut. But I don't know how that would work computationally. Using wide bounds seems okay.

cc @zfornier this fixes the StrengthenedConicDuality case, but not the LagrangianDuality. I obviously need to play with your example more.

zfornier commented 3 years ago

Since with the StrengthenedConicDuality option, SDDP finds a feasible solution, respecting the binary constraint, I would like to understand better how it works, how this parameter changes the way SDDP handles binary variables. Would you have some articles in particular to recommend to me?

On Mon, Aug 23, 2021 at 11:13 AM Oscar Dowson @.***> wrote:

StrengthenedConicDuality can't use the higher bounds because the continuous dual solution is likely infeasible. If the bounds are too tight, then we'll get an incorrect dual objective value.

There must be something like adding a feasibility cut. But I don't know how that would work computationally. Using wide bounds seems okay.

cc @zfornier https://github.com/zfornier this fixes the StrengthenedConicDuality case, but not the LagrangianDuality. I obviously need to play with your example more.

You can view, comment on, or merge this pull request online at:

https://github.com/odow/SDDP.jl/pull/457 Commit Summary

  • Fix bug in lagrangian duality

File Changes

Patch Links:

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/odow/SDDP.jl/pull/457, or unsubscribe https://github.com/notifications/unsubscribe-auth/AMV7TEWCU2FWA3EAFWFDVX3T6IGMTANCNFSM5CUESF6Q . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email .

odow commented 3 years ago

I should write a tutorial for the documentation.

I find how SDDiP is presented as a concept in the literature confusing.

We have these subproblems:

image

and we're trying to find a feasible dual solution and corresponding dual objective value for the slope and intercept of the cut respectively.

You should probably be able to find a feasible solution with the default ContinuousConicDuality option as well. I changed how we handle integer variables in the forward pass during training.

zfornier commented 3 years ago

Yes ok, I need to read more about all of this, thank you!

On Tue, Aug 24, 2021 at 10:32 PM Oscar Dowson @.***> wrote:

I should write a tutorial for the documentation.

I find how SDDiP is presented as a concept in the literature confusing.

We have these subproblems: [image: image] https://user-images.githubusercontent.com/8177701/130685165-a75d5efb-abab-469c-98a0-ff18bd739444.png and we're trying to find a feasible dual solution and corresponding dual objective value for the slope and intercept of the cut respectively.

You should probably be able to find a feasible solution with the default ContinuousConicDuality option as well. I changed how we handle integer variables in the forward pass during training.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/odow/SDDP.jl/pull/457#issuecomment-904954193, or unsubscribe https://github.com/notifications/unsubscribe-auth/AMV7TETDRAUP3NJLM66EP2TT6P6VPANCNFSM5CUESF6Q . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&utm_campaign=notification-email .