org.ddolibscala.modeling

Default implementation of the FastLowerBound trait that always returns Int.MinValue

This implementation can be used as a placeholder or a fallback when no meaningful fast lower bound heuristic is available for a given problem. It effectively disables lower bound pruning since the returned value is * the smallest possible integer.

Default implementation of the StateRanking trait where all the states are equals.

This implementation can be used as a placeholder or a fallback when no meaningful ranking is available for a given problem.

Defines a dominance relation used to compare and prune states during the exploration of decision diagrams or search spaces.

Dominance relation provides a way to determine whether one state of the problem is at least as good as (i.e., dominates) another, allowing the solver to discard redundant or inferior subproblems.

The dominance check is an essential optimization mechanism in decision diagram–based solvers, as it helps reduce the search space by recognizing equivalent or dominated states that do not need to be further expanded.

Heuristic defining a fast lower bound for states

Problem defines the state space, the transitions between states induced by decisions, and the objective values associated with those transitions. Implementations provide the essential operations required by solvers.

Defines the relaxation that may be applied to the given problem. In particular, the merge method from this trait defines how the nodes of a layer may be combined to provide an upper bound approximation standing for an arbitrarily selected set of nodes.

A state ranking is used to order the states and decides the ones that are kept and the ones that are merged/deleted when a relaxation/restriction occurs.

In this context, a state ranking is nothing but an ordering on the states which is defined in the form of a comparator. The solvers and MDD should interpret compare(a, b) > 0 as a should have a higher chance of being kept intact while b should have a higher chance of being merged.