Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix cut sharing in a graph with zero-probability arcs #797

Open
wants to merge 9 commits into
base: master
Choose a base branch
from

Conversation

odow
Copy link
Owner

@odow odow commented Oct 23, 2024

Closes #796

@adow031 want to test this branch?

TODO

  • add tests

src/algorithm.jl Outdated Show resolved Hide resolved
@odow
Copy link
Owner Author

odow commented Oct 23, 2024

It'd be helpful if I could spell

Copy link

codecov bot commented Oct 23, 2024

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 93.58%. Comparing base (cc604a4) to head (68b40de).

Additional details and impacted files
@@            Coverage Diff             @@
##           master     #797      +/-   ##
==========================================
+ Coverage   93.54%   93.58%   +0.03%     
==========================================
  Files          26       26              
  Lines        3519     3521       +2     
==========================================
+ Hits         3292     3295       +3     
+ Misses        227      226       -1     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

@adow031
Copy link

adow031 commented Oct 23, 2024

This issue appears to be resolved.

But looking at the fix: is the result that the there's no longer cut sharing when there are some 0 probabilities? I would prefer that the code just inefficiently solved children with 0 probabilities than didn't share cuts.

(A user would always have the option to not include an arc with 0 probability if there's a preference for reducing the number of solves.)

@odow
Copy link
Owner Author

odow commented Oct 23, 2024

Currently we share cuts iff they have the identical set of children. We could improve that to nodes with have a subset of children. So yes, this might result in a less efficient solve; probably somewhere in between setting refine_at_similar_nodes = false, depending on the structure of the zeros.

@odow
Copy link
Owner Author

odow commented Oct 23, 2024

But yeah, I'll take another go at fixing this.

@odow
Copy link
Owner Author

odow commented Oct 25, 2024

Okay, I'm taking a look at this.

The issue is

SDDP.jl/src/algorithm.jl

Lines 755 to 757 in f921657

if isapprox(child.probability, 0.0; atol = 1e-6)
continue
end

which we added in #224

The fix of just adding this is surprisingly subtle, because risk measures now need to deal with values that have zero probability mass

WorstCase is the obvious one, but it already checks this:

for (index, (probability, observation)) in
enumerate(zip(original_probability, objective_realizations))
if probability > 0.0
if (is_minimization && observation > worst_observation) ||
(!is_minimization && observation < worst_observation)
worst_index = index
worst_observation = observation
end
end

@odow
Copy link
Owner Author

odow commented Oct 25, 2024

Belief states broke. I assume because something weird happens if you try to update the belief from somewhere that it was impossible to come from. There's a subtle distinction between ambiguity sets and nodes with similar children...

@@ -478,16 +478,8 @@ function MarkovianGraph(transition_matrices::Vector{Matrix{Float64}})
for markov_state in 1:size(transition, 2)
for last_markov_state in 1:size(transition, 1)
probability = transition[last_markov_state, markov_state]
if 0.0 < probability <= 1.0
Copy link
Owner Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So @adow031: should we add zero-probability arcs for Markov transition matrices or keep the graph sparse?

@odow
Copy link
Owner Author

odow commented Nov 7, 2024

Bump @adow031 interested in your thoughts

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Cut sharing with Markov policy graph
2 participants