Package org.jacop.search

Class Shaving<T extends IntVar>

  • All Implemented Interfaces:
    ConsistencyListener, ExitChildListener<T>
    public class Shaving<T extends IntVar>
extends java.lang.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.8

    • Field Detail

      • shavingConstraints

        java.util.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 java.util.HashSet<IntVar> varsOfFailedConstraint
        It stores the variables of the last failed constraints.

      • wrongDecisionEncountered

        boolean wrongDecisionEncountered

      • 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

        java.util.List<java.util.Map<IntVar,​java.util.LinkedHashSet<java.lang.Integer>>> shavable

      • notShavable

        java.util.Map<IntVar,​java.util.LinkedHashSet<java.lang.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 Detail

      • Shaving

        public Shaving()

    • Method Detail

      • 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.

      • 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,
                        java.lang.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.