Trait ddo::Relaxation

pub trait Relaxation {
    type State;

    // Required methods
    fn merge(
        &self,
        states: &mut dyn Iterator<Item = &Self::State>
    ) -> Self::State;
    fn relax(
        &self,
        source: &Self::State,
        dest: &Self::State,
        new: &Self::State,
        decision: Decision,
        cost: isize
    ) -> isize;

    // Provided method
    fn fast_upper_bound(&self, _state: &Self::State) -> isize { ... }
}

A relaxation encapsulates the relaxation $\Gamma$ and $\oplus$ which are necessary when compiling relaxed DDs. These operators respectively relax the weight of an arc towards a merged node, and merges the staet of two or more nodes so as to create a new inexact node.

Required Associated Types

type State

Similar to the DP model of the problem it relaxes, a relaxation operates on a set of states (the same as the problem).

Required Methods

fn merge(&self, states: &mut dyn Iterator<Item = &Self::State>) -> Self::State

This method implements the merge operation: it combines several states and yields a new state which is supposed to stand for all the other merged states. In the mathematical model, this operation was denoted with the $\oplus$ operator.

fn relax( &self, source: &Self::State, dest: &Self::State, new: &Self::State, decision: Decision, cost: isize ) -> isize

This method relaxes the cost associated to a particular decision. It is called for any arc labeled decision whose weight needs to be adjusted because it is redirected from connecting src with dst to connecting src with new. In the mathematical model, this operation is denoted by the operator $\Gamma$.

Provided Methods

fn fast_upper_bound(&self, _state: &Self::State) -> isize

Returns a very rough estimation (upper bound) of the optimal value that could be reached if state were the initial state

Implementors