Trait ddo::WidthHeuristic

source · 
pub trait WidthHeuristic<State> {
    // Required method
    fn max_width(&self, state: &SubProblem<State>) -> usize;
}
Expand description

This trait encapsulates the behavior of the heuristic that determines the maximum permitted width of a decision diagram.

§Technical Note:

Just like Problem, Relaxation and StateRanking, the WidthHeuristic trait is generic over States. However, rather than using the same ‘associated-type’ mechanism that was used for the former three types, WidthHeuristic uses a parameter type for this purpose (the type parameter approach might feel more familiar to Java or C++ programmers than the associated-type).

This choice was motivated by two factors:

  1. The Problem, Relaxation and StateRanking are intrinsically tied to one type of state. And thus, the State is really a part of the problem/relaxation itself. Therefore, it would not make sense to define a generic problem implementation which would be applicable to all kind of states. Instead, an implementation of the Problem trait is the concrete implementation of a DP model (same argument holds for the other traits).

  2. On the other hand, it does make sense to define a WidthHeuristic implementation which is applicable regardless of the state of the problem which is currently being solved. For instance, the ddo framework offers the Fixed and NbUnassigned width heuristics which are independent of the problem. The Fixed width heuristic imposes that the maximum layer width be constant across all compiled DDs whereas NbUnassigned lets the maximum width vary depending on the number of problem variables which have already been decided upon.

Required Methods§

source

fn max_width(&self, state: &SubProblem<State>) -> usize

Estimates a good maximum width for an MDD rooted in the given state

Implementors§