Class Search


  • public class Search
    extends Object
    • Constructor Detail

      • Search

        public Search()
    • Method Detail

      • lastConflict

        public static <V extends VariableAbstractStrategy<V> lastConflict​(AbstractStrategy<V> formerSearch)
        Use the last conflict heuristic as a pluggin to improve a former search heuristic Should be set after specifying a search strategy.
        Returns:
        last conflict strategy
      • bestBound

        public static AbstractStrategy<IntVar> bestBound​(AbstractStrategy<IntVar> formerSearch)
        Search heuristic combined with a constraint performing strong consistency on the next decision variable and branching on the value with the best objective bound (for optimization) and branches on the lower bound for SAT problems. BEWARE: ONLY FOR INTEGERS (lets the former search work for other variable types)
        Parameters:
        formerSearch - default search to branch on variables (defines the variable selector and the value selector when this does not hold)
        Returns:
        best bound strategy
      • lastConflict

        public static <V extends VariableAbstractStrategy<V> lastConflict​(AbstractStrategy<V> formerSearch,
                                                                            int k)
        Use the last conflict heuristic as a pluggin to improve a former search heuristic Should be set after specifying a search strategy.
        Parameters:
        k - the maximum number of conflicts to store
        Returns:
        last conflict strategy
      • conflictOrderingSearch

        public static <V extends VariableAbstractStrategy<V> conflictOrderingSearch​(AbstractStrategy<V> formerSearch)
        Use the conflict ordering search as a pluggin to improve a former search heuristic Should be set after specifying a search strategy.
        Returns:
        last conflict strategy
      • greedySearch

        public static AbstractStrategy greedySearch​(AbstractStrategy search)
        Make the input search strategy greedy, that is, decisions can be applied but not refuted.
        Parameters:
        search - a search heuristic building branching decisions
        Returns:
        a greedy form of search
      • sequencer

        public static AbstractStrategy sequencer​(AbstractStrategy... searches)
        Apply sequentialy enumeration strategies. Strategies are considered in input order. When strategy i returns null (all variables are instantiated) the i+1 ones is activated.
        Parameters:
        searches - ordered set of enumeration strategies
      • setVarSearch

        public static SetStrategy setVarSearch​(VariableSelector<SetVar> varS,
                                               SetValueSelector valS,
                                               boolean enforceFirst,
                                               SetVar... sets)
        Generic strategy to branch on set variables
        Parameters:
        varS - variable selection strategy
        valS - integer selection strategy
        enforceFirst - branching order true = enforce first; false = remove first
        sets - SetVar array to branch on
        Returns:
        a strategy to instantiate sets
      • setVarSearch

        public static SetStrategy setVarSearch​(SetVar... sets)
        strategy to branch on sets by choosing the first unfixed variable and forcing its first unfixed value
        Parameters:
        sets - variables to branch on
        Returns:
        a strategy to instantiate sets
      • realVarSearch

        public static RealStrategy realVarSearch​(VariableSelector<RealVar> varS,
                                                 RealValueSelector valS,
                                                 double epsilon,
                                                 boolean leftFirst,
                                                 RealVar... rvars)
        Generic strategy to branch on real variables, based on domain splitting. A real decision is like:
        • left branch: X ≤ v
        • right branch: X ≥ v + e
        where 'e' is given by epsilon.

        Parameters:
        varS - variable selection strategy
        valS - strategy to select where to split domains
        epsilon - gap for refutation
        rvars - RealVar array to branch on
        leftFirst - select left range first
        Returns:
        a strategy to instantiate reals
      • realVarSearch

        public static RealStrategy realVarSearch​(double epsilon,
                                                 RealVar... reals)
        strategy to branch on real variables by choosing sequentially the next variable domain to split in two, wrt the middle value. A real decision is like:
        • left branch: X ≤ v
        • right branch: X ≥ v + e
        where 'e' is given by epsilon.

        Parameters:
        epsilon - gap for refutation
        reals - variables to branch on
        Returns:
        a strategy to instantiate real variables
      • realVarSearch

        public static RealStrategy realVarSearch​(VariableSelector<RealVar> varS,
                                                 RealValueSelector valS,
                                                 boolean leftFirst,
                                                 RealVar... rvars)
        Generic strategy to branch on real variables, based on domain splitting. A real decision is like:
        • left branch: X ≤ v
        • right branch: X ≥ v + epsilon
        where epsilon is given or equal to the smallest precision among rvars divide by 10.

        Parameters:
        varS - variable selection strategy
        valS - strategy to select where to split domains
        leftFirst - select left range first
        rvars - RealVar array to branch on
        Returns:
        a strategy to instantiate reals
      • realVarSearch

        public static RealStrategy realVarSearch​(RealVar... reals)
        strategy to branch on real variables by choosing sequentially the next variable domain to split in two, wrt the middle value. A real decision is like:

        Parameters:
        reals - variables to branch on
        Returns:
        a strategy to instantiate real variables
      • intVarSearch

        public static IntStrategy intVarSearch​(VariableSelector<IntVar> varSelector,
                                               IntValueSelector valSelector,
                                               DecisionOperator<IntVar> decisionOperator,
                                               IntVar... vars)
        Builds your own search strategy based on binary decisions.
        Parameters:
        varSelector - defines how to select a variable to branch on.
        valSelector - defines how to select a value in the domain of the selected variable
        decisionOperator - defines how to modify the domain of the selected variable with the selected value
        vars - variables to branch on
        Returns:
        a custom search strategy
      • intVarSearch

        public static IntStrategy intVarSearch​(VariableSelector<IntVar> varSelector,
                                               IntValueSelector valSelector,
                                               IntVar... vars)
        Builds your own assignment strategy based on binary decisions. Selects a variable X and a value V to make the decision X = V. Note that value assignments are the public static decision operators. Therefore, they are not mentioned in the search heuristic name.
        Parameters:
        varSelector - defines how to select a variable to branch on.
        valSelector - defines how to select a value in the domain of the selected variable
        vars - variables to branch on
        Returns:
        a custom search strategy
      • intVarSearch

        public static AbstractStrategy<IntVar> intVarSearch​(IntVar... vars)
        Builds a default search heuristics of integer variables Variable selection relies on domOverWDegSearch(IntVar...) Value selection relies on InDomainBest for optimization and InDomainMin for satisfaction
        Parameters:
        vars - variables to branch on
        Returns:
        a default search strategy
      • domOverWDegSearch

        public static AbstractStrategy<IntVar> domOverWDegSearch​(IntVar... vars)
        Assignment strategy which selects a variable according to DomOverWDeg and assign it to its lower bound
        Parameters:
        vars - list of variables
        Returns:
        assignment strategy
      • activityBasedSearch

        public static AbstractStrategy<IntVar> activityBasedSearch​(IntVar... vars)
        Create an Activity based search strategy.

        "Activity-Based Search for Black-Box Constraint Propagramming Solver", Laurent Michel and Pascal Van Hentenryck, CPAIOR12.
        Uses public static parameters (GAMMA=0.999d, DELTA=0.2d, ALPHA=8, RESTART=1.1d, FORCE_SAMPLING=1)

        Parameters:
        vars - collection of variables
        Returns:
        an Activity based search strategy.
      • randomSearch

        public static IntStrategy randomSearch​(IntVar[] vars,
                                               long seed)
        Randomly selects a variable and assigns it to a value randomly taken in - the domain in case the variable has an enumerated domain - {LB,UB} (one of the two bounds) in case the domain is bounded
        Parameters:
        vars - list of variables
        seed - a seed for random
        Returns:
        assignment strategy
      • objectiveStrategy

        public static AbstractStrategy<IntVar> objectiveStrategy​(IntVar objective,
                                                                 OptimizationPolicy optPolicy)
        Defines a branching strategy over the objective variable Note that it is only activated after a first solution. This should be completed with another strategy with a larger scope.
        Parameters:
        objective - objective variable
        optPolicy - policy to adopt for the optimization process
        Returns:
        a assignment strategy
      • inputOrderLBSearch

        public static IntStrategy inputOrderLBSearch​(IntVar... vars)
        Assigns the first non-instantiated variable to its lower bound.
        Parameters:
        vars - list of variables
        Returns:
        int strategy based on value assignments
      • inputOrderUBSearch

        public static IntStrategy inputOrderUBSearch​(IntVar... vars)
        Assigns the first non-instantiated variable to its upper bound.
        Parameters:
        vars - list of variables
        Returns:
        assignment strategy
      • minDomLBSearch

        public static IntStrategy minDomLBSearch​(IntVar... vars)
        Assigns the non-instantiated variable of smallest domain size to its lower bound.
        Parameters:
        vars - list of variables
        Returns:
        assignment strategy
      • minDomUBSearch

        public static IntStrategy minDomUBSearch​(IntVar... vars)
        Assigns the non-instantiated variable of smallest domain size to its upper bound.
        Parameters:
        vars - list of variables
        Returns:
        assignment strategy
      • defaultSearch

        public static AbstractStrategy defaultSearch​(Model model)
        Creates a default search strategy for the given model. This heuristic is complete (handles IntVar, BoolVar, SetVar and RealVar)
        Parameters:
        model - a model requiring a default search strategy
      • ibexSolving

        public static AbstractStrategy ibexSolving​(Model model)

        Create a strategy which lets Ibex terminates the solving process for the CSP, once all integer variables have been instantiated.

        Note that if the system is not constrained enough, there can be an infinite number of solutions.

        For example, solving the function
        x,y in [0.0,1.0] with
        x + y = 1.0
        will return x,y in [0.0,1.0] and not a single solution.

        If one wants a unique solution, calling realVarSearch(RealVar...) should be considered.

        Parameters:
        model - declaring model
        Returns:
        a strategy that lets Ibex terminates the solving process.