Cut sharing with Markov policy graph

[adow031]

I've got a SDDP model with a Markov chain used to define states and the transitions between them at each stage.

After noticing some strange behaviour in the simulated policy, the model was retrained with refine_at_similar_nodes set to false. This resolved the issue.

I've tracked the cause of the problem to there being 0 probabilities between some pairs of states at various stages. This seems to lead to SDDP not solving the model for those states, but the dual variable from the unsolved models are still being used to form cuts at other nodes in the policy graph.

I can't post a MFE here, but the above description will hopefully allow this issue to be reproduced.

[odow]

What is the issue exactly? "strange behavior" isn't very descriptive

[odow]

This, it seems to lead to SDDP not solving the model for those states, but the dual variable from the unsolved models are still being used to form cuts at other nodes at other nodes in the policy graph.

Oooo, now I understand. The node will have a cached dual solution from a previous solve, but the incoming state variables won't line up.

[adow031]

That makes sense. I had tried to fix it myself, but decided to just post here.

[odow]

I thought I'd fixed the 0 probability arc thing. It's come up before. I can't immediately find the issue though

[odow]

Note to self: it's probably sufficient to just exclude zero-probability arcs here:

SDDP.jl/src/algorithm.jl

Lines 57 to 80 in 4091155

	# Internal function: returns a dictionary with a key for each node, where the
	# value is a list of other nodes that contain the same children. This is useful
	# because on the backward pass we can add cuts to nodes with the same children
	# without having to re-solve the children.
	function get_same_children(model::PolicyGraph{T}) where {T}
	tmp = Dict{Set{T},Set{T}}()
	for (key, node) in model.nodes
	children = Set(child.term for child in node.children)
	if length(children) == 0
	continue
	elseif haskey(tmp, children)
	push!(tmp[children], key)
	else
	tmp[children] = Set{T}([key])
	end
	end
	same_children = Dict{T,Vector{T}}(key => T[] for key in keys(model.nodes))
	for set in values(tmp)
	for v in set
	same_children[v] = collect(setdiff(set, Ref(v)))
	end
	end
	return same_children
	end