Package org.jacop.search

Class Shaving<T extends IntVar>

java.lang.Object
org.jacop.search.Shaving<T>
All Implemented Interfaces:
ConsistencyListener, ExitChildListener<T>
public class Shaving<T extends IntVar> extends Object implements ExitChildListener<T>, ConsistencyListener
Defines functionality of shaving. Plugin in this object to search to change your depth first search to a search with shaving capabilities.

Shaving

Each search level stores the variable value pairs which were shaved at a given level.

Shaving speculation.

The right child is using all the shavable pairs from the subtree rooted at the sibling of the current search node. If shaving fails then it is recorded in non shavable.

Not-shavable speculation

Every time a variable value pair is being schedule for shavability check then it is checked if that pair was not already checked for shavability before with a negative results. If so, then check is not performed but also entry in not-shavable is removed.

If variable value pair proofs to be not shavable then this variable value pair is recorded into Not-shavable speculation.

Quick shave - upon exiting any subtree the variable value pair which was choosen at the root of that subtree is recorded as shavable variable value pair.

Version:
4.10

  • Field Details

    • shavingConstraints

      List<Constraint> shavingConstraints
      It contains list of constraints which suggest shaving explorations.

    • leftChild

      boolean leftChild
      It specifies if the search is in the left child.

    • store

      Store store
      It specifies current store, so shaving can obtained information about recent failed constraint.

    • recentlyFailedConstraint

      Constraint recentlyFailedConstraint

    • leftChildShaving

      boolean leftChildShaving

    • onlyFailedConstraint

      public boolean onlyFailedConstraint
      It specifies if only the last failed constraint is allowed to suggest shaving values.

    • rightChild

      boolean rightChild

    • onlyIntVarsOfFailedConstraint

      public boolean onlyIntVarsOfFailedConstraint
      It specifies if only variables in the scope of the last failed constraint are allowed to be used in shaving attempts.

    • varsOfFailedConstraint

      public HashSet<IntVar> varsOfFailedConstraint
      It stores the variables of the last failed constraints.

    • wrongDecisionEncountered

      boolean wrongDecisionEncountered

    • exitChildListeners

      private ExitChildListener<T extends IntVar>[] exitChildListeners

    • consistencyListeners

      private ConsistencyListener[] consistencyListeners

    • quickShave

      public boolean quickShave
      It specifies if the quickShave approach should be also used. Quickshave uses variable-value pairs which lead to wrong decisions as shaving values higher in the search tree (until the first time shaving attempt for this value fails).

    • leftChildWrongDecision

      private boolean leftChildWrongDecision

    • depth

      private int depth

    • shavable

      List<Map<IntVar,LinkedHashSet<Integer>>> shavable

    • notShavable

      Map<IntVar,LinkedHashSet<Integer>> notShavable

    • successes

      public int successes
      It stores number of successful shaving attempts.

    • failures

      public int failures
      It stores number of failed shaving attempts.

  • Constructor Details

    • Shaving

      public Shaving()

  • Method Details

    • leftChild

      public boolean leftChild(IntVar var, int value, boolean status)
      Description copied from interface: ExitChildListener
      It is executed after exiting the left child.
      Specified by:
      leftChild in interface ExitChildListener<T extends IntVar>
      Parameters:
      var - variable used in the choice point.
      value - value used in the choice point.
      status - true if the solution was found in the child subtree, false otherwise.
      Returns:
      true if the search should continue undisturbed, false if it should exit the current node with false

    • leftChild

      public boolean leftChild(PrimitiveConstraint choice, boolean status)
      Description copied from interface: ExitChildListener
      It is executed after exiting the left child.
      Specified by:
      leftChild in interface ExitChildListener<T extends IntVar>
      Parameters:
      choice - primitive constraint used as the base of the choice point.
      status - true if the solution was found in the child subtree, false otherwise.
      Returns:
      true if the search should continue undisturbed to the right node, false if it should exit the current node with false

    • rightChild

      public void rightChild(IntVar var, int value, boolean status)
      Description copied from interface: ExitChildListener
      It is executed after exiting the right child.
      Specified by:
      rightChild in interface ExitChildListener<T extends IntVar>
      Parameters:
      var - variable used in the choice point.
      value - value used in the choice point.
      status - true if the solution was found in the child subtree, false otherwise. exit the current node with false

    • rightChild

      public void rightChild(PrimitiveConstraint choice, boolean status)
      Description copied from interface: ExitChildListener
      It is executed after exiting the right child.
      Specified by:
      rightChild in interface ExitChildListener<T extends IntVar>
      Parameters:
      choice - primitive constraint used as the base of the choice point.
      status - true if the solution was found in the child subtree, false otherwise. exit the current node with false

    • setChildrenListeners

      public void setChildrenListeners(ConsistencyListener[] children)
      Description copied from interface: ConsistencyListener
      Each of the child listeners will be called and the return code from them will be combined (taken into account) by a parent).
      Specified by:
      setChildrenListeners in interface ConsistencyListener
      Parameters:
      children - the children listeners attached to this listener.

    • setChildrenListeners

      public void setChildrenListeners(ExitChildListener<T>[] children)
      Description copied from interface: ExitChildListener
      It sets the children listeners for the current listener.
      Specified by:
      setChildrenListeners in interface ExitChildListener<T extends IntVar>
      Parameters:
      children - array containing children listeners.

    • setChildrenListeners

      public void setChildrenListeners(ConsistencyListener child)
      Description copied from interface: ConsistencyListener
      Setting one child listener.
      Specified by:
      setChildrenListeners in interface ConsistencyListener
      Parameters:
      child - the only child listener added to this consistency listener.

    • setChildrenListeners

      public void setChildrenListeners(ExitChildListener<T> child)
      Description copied from interface: ExitChildListener
      It adds one child listener.
      Specified by:
      setChildrenListeners in interface ExitChildListener<T extends IntVar>
      Parameters:
      child - added child listener.

    • executeAfterConsistency

      public boolean executeAfterConsistency(boolean consistent)
      Description copied from interface: ConsistencyListener
      It is executed right after consistency of the current search node. Returning true when the parameter was false is not advised as things like invalid solutions can be found.
      Specified by:
      executeAfterConsistency in interface ConsistencyListener
      Parameters:
      consistent - specifies if the consistency call returned true or false.
      Returns:
      true if the search should continue, false if the search should act as the consistency returned false.

    • checkIfShavable

      boolean checkIfShavable(IntVar var, Integer val)

    • addShavingConstraint

      public void addShavingConstraint(Constraint c)
      It adds shaving constraint to the list of constraints guiding shaving.
      Parameters:
      c - constraint which is added to the list of guiding constraints.

    • setStore

      public void setStore(Store store)
      It specifies the constraint store in which context the shaving will take place.
      Parameters:
      store - constraint store.