When there are inactive chance states (zero probability) in the model, the model currently creates path probability variables and fixes them to zero. We could avoid creating the fixed variables altogether by using a dictionary (as a sparse multidimensional array) instead of (a dense, multidimensional) array of path probability variables. We can then efficiently create decision models (faster and less memory usage) create decision models when there are many inactive chance states. Also, there is less unnecessary variables or constraints for the solver to remove.

These improvements do not require changes to API, only some changes to the internals of the following functions in decision_model.jl:

• path_probability_variables: Create path probability variables by deterministically iterating over paths without inactive chance states. Store variable in the dictionary. We also need to implement the deterministic iterator.
• probability_cut
• active_paths_cut
• expected_value
• conditional_value_at_risk

We need to check that the changes do not cause any performance regressions.

Benchmarks for decision programming on different kinds of influence diagrams. Here are some ideas on what to measure:

• Hard lower bound versus soft lower bound with the positive path utility for path probability variables.
• The effect of lazy cuts on performance.
• Effects of limited memory influence diagrams on performance (compared to no-forgetting)
• Performance comparison between the expected value and conditional value at risk.
• Different Gurobi settings.
• Memory usage might also be interesting.

Measuring performance requires random sampling of influence diagrams with different attributes such as the number of nodes, limited memory, and inactive chance nodes. The random.jl module is suited for this purpose. We also need to agree on good metrics for the benchmarks.

@jandelmi mentioned analyzing the model generated by Gurobi, which might be useful here as well.

backend = JuMP.backend(model)
gmodel = backend.optimizer.model.inner
Gurobi.write_model(gmodel, "gurobi_model.lp")

Nodes and states should have optional name tags that would be displayed when printing results. Tags are strings, preferably a maximum of 3 characters long, and default to the node or state index value. We should warn users that if they exceed the limit, the printing output may not display nicely.

As demonstrated by the contingent portfolio programming example, the path utility functions allow using numerical, linear, and integer-linear JuMP expressions as values for path utilities when forming positive path utility and conditional value-at-risk. Linear path utilities lead to quadratic formulations of expected value and conditional value-at-risk, which Gurobi can solve.

We can modify consequences such that it allows both real numbers and JuMP variables as values. The variables must have lower and upper bounds.

const RealOrVar = Union{<:Real, VariableRef}

struct Consequences{N} <: AbstractArray{RealOrVar, N}
    j::Node
    data::Array{RealOrVar, N}
end

The PathUtility <: AbstractPathUtility structure should have methods for:

• querying the expression for a path, and
• querying a value for a path after optimization is complete.

Something similar to this snippet:

struct PathUtility <: AbstractPathUtility
    data::Array{AffExpr}
end

Base.getindex(U::PathUtility, i::Int) = getindex(U.data, i)
Base.getindex(U::PathUtility, I::Vararg{Int,N}) where N = getindex(U.data, I...)
(U::PathUtility)(s::Path) = value.(U[s...])

We need to modify the expected value objective as follows:

function expected_value(model::Model, π_s::Array{VariableRef}, S::States, U::AbstractPathUtility)
    @expression(model, sum(π_s[s...] * U[s...] for s in paths(S)))
end

Then creating a path utility and setting an expected value objective works as follows:

function PathUtility(model, V, Y, S)
    # ...
    PathUtility([@expression(model, ...) for s in paths(S)])
end

U = PathUtility(model, V, Y, S)
EV = expected_value(model, π_s, S, U)
@objective(model, Max, EV)

We need optimization formulations for determining:

• minimum path utility,
• maximum path utility, and
• the smallest positive difference between path utilities (if the conditional value-at-risk formulation can be extended to use linear path utility values).

We can supply these values as arguments to the positive path utility and conditional value-at-risk functions.

We can also use path utilities as objectives with positive expected value as a constraint by allowing expressions.

The visual representation of influence diagrams requires visualizing nodes, information sets, and states. Nodes should have distinct shapes and colors. We should represent them in depth-wise order from left to right. For example:

• Chance nodes: Circle, light-blue, stroke-width 3
• Decision nodes: Square, light-green, stroke-width 3
• Value node: Diamond (rhombus), orange, stroke-width 3
• Information sets of chance and decision nodes: Normal arrows
• Information sets of value nodes: Dashed arrows
• Labels: Node ... <br> States: ...

We can create diagrams programmatically using Mermaid.js:

graph LR
    subgraph Chance and Decision Nodes
        %% Chance nodes
        1((Node: 1 <br> States: 2))
        2((Node: 2 <br> States: 2))
        1 --> 2
        class 1,2 chance

        %% Decision nodes
        3[Node: 3 <br> States: 2]
        4[Node: 4 <br> States: 3]
        1 --> 3
        1 & 2 & 3 --> 4
        class 3,4 decision
    end

    subgraph Value Nodes
        %% Value nodes
        5{Node 5}
        2 & 4 -.-> 5
        class 5 value
    end

    %% Styles
    classDef chance fill:lightblue,stroke:blue,stroke-width:3px;
    classDef decision fill:lightgreen,stroke:green,stroke-width:3px;
    classDef value fill:orange,stroke:darkorange,stroke-width:3px;

Mermaid syntax is explained in the documentation.

Designing influence diagrams is easier using diagrams.net. We can also import Mermaid diagrams to diagrams.net.

In some models the path probabilities may be very small. This can happen especially if many of the nodes have a large number of states. In this case the solver can struggle to find a solution. This can be helped by scaling the path probabilities with a scale factor. Note that after solving the problem the solution also needs to be scaled back using the same scale factor. This functionality was used when solving the CHD preventative care allocation problem.

This requires adding the scaling factor as a parameter and some internal changes to the following functions in decision_model.jl:

• path_probability_variable
• PathProbabilityVariables
• probability_cut
• active_paths_cut
• expected_value
• conditional_value_at_risk

The DefaultPathProbability constructor does not check that the number of chance nodes and the number of probability matrices are the same. If a probability matrix is not added for all chance nodes, this produces strange behavior, but no error.

The appendix page should contain the following sections:

• Proofs: The documentation should be self-contained, that is, not rely on external references for proofs of the formulation.
• Notation: List of notation with references to the implementations in the code.

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Add an example on how probability_scale_factor works, perhaps illustrating the benefit of it in the performance in the n-monitoring example?

This description will be about the probability cut since it's the one I've been debugging, but some of these points will also need to be addressed for the active paths cut. I created a branch probability_cut with some quick fixes, but we might want to think about these some more.

The tolerance (epsilon) doesn't work as an absolute tolerance

• Really simple example: you participate in a lottery where you have an 80% chance to win one euro and a 20% chance to lose four. The influence diagram corresponding to this problem is a single chance node and a value node, you don't even get to decide whether or not you want to participate. Thus, there are two paths and the solution is trivial: both of them should be active. What this version of the probability cut does is set epsilon to 0.2, then check if the probability sum is between 0.8 and 1.2 (isapprox with atol=0.2). The solution where we ignore the possibility of losing is valid, and we get expected value of one euro.
• In an older implementation of the framework, the probability sum is calculated in a different way. First the active paths are defined as those whose probability is at least epsilon, then πsum is calculated as the sum of probabilities π for those active paths.
• The quick fix I did was to remove the epsilon and use the default tolerance for the isapprox function

The flag breaks things for an unknown reason

• In general, it is a good idea to avoid adding the same constraint multiple times and the flag should thus be a good idea
• According to the documentation, setting the Gurobi parameter LazyConstraints=1 should "avoid certain reductions and transformations that are incompatible with lazy constraints"
• In practice, it seems like the lazy constraint might be added before presolving the model, and dropped in the presolving process despite correctly setting the parameter.
• The quick fix I did was to remove the flag.

Possible incompatibility between forbidden paths and probability cuts?

• In a special case, the upper and lower bound might not converge. This happened when using the hard lower bound constraints, forbidden paths and lazy probability cuts at the same time. The primal bound converged to the correct solution without the probability cuts because of the hard lower bound constraints, but the dual bound was zero. The problem was solved by deactivating the hard lower bound constraints. Need to look into this more.

We need a rigorous definition of symmetric influence diagrams. Influence diagrams which are not symmetric are asymmetric. If an influence diagram has inactive chance states, it can be asymmetric, but I don't think it's a sufficient condition.

We can only use activate_path_cut on symmetric influence diagrams where the exact number of active paths is constant.

Currently, the package doesn't allow the creation of chances of decision nodes with a single state

ERROR: DomainError with Each chance and decision node should have more than one state.

This can be useful in some cases, e.g., having a degenerate chance node to simulate different scenarios in parallel. I think it can be useful to just show a warning instead of stopping the code when this situation occurs.