Package org.ddolib.modeling

Interface Relaxation<T>

Type Parameters:
T - the type of state
All Known Implementing Classes:
ALPRelax, BKSRelax, GRRelax, KSRelax, LCSRelax, Max2SatRelax, MaxCoverRelax, MCPRelax, MispRelax, MKSRelax, MSCTRelax, PSRelax, SMICRelax, SRFLPRelax, TSPRelax, TSPTWRelax, TSRelax
public interface Relaxation<T>
This is the second most important abstraction that a client should provide when using this library. It defines the relaxation that may be applied to the given problem. In particular, the merge_states method from this trait defines how the nodes of a layer may be combined to provide a lower bound approximation standing for an arbitrarily selected set of nodes.

Again, the type parameter `T` denotes the type of the states.

  • Method Summary

    Modifier and Type
    Method
    Description
    T
    mergeStates(Iterator<T> states)
    Merges the given states to create a NEW state which is an over approximation of all the covered states.
    double
    relaxEdge(T from, T to, T merged, Decision d, double cost)
    Relaxes the edge that used to go from `from` to `to` and computes the cost of the new edge going from `from` to `merged`.

  • Method Details

    • mergeStates

      T mergeStates(Iterator<T> states)
      Merges the given states to create a NEW state which is an over approximation of all the covered states.
      Parameters:
      states - the set of states that must be merged
      Returns:
      a new state which is an over approximation of all the considered `states`.

    • relaxEdge

      double relaxEdge(T from, T to, T merged, Decision d, double cost)
      Relaxes the edge that used to go from `from` to `to` and computes the cost of the new edge going from `from` to `merged`. The decision which is being relaxed is given by `d` and the value of the not relaxed arc is `cost`.
      Parameters:
      from - the origin of the relaxed arc
      to - the destination of the relaxed arc (before relaxation)
      merged - the destination of the relaxed arc (after relaxation)
      d - the decision which is being challenged
      cost - the cost of the not relaxed arc which used to go from `from` to `to`
      Returns: