Labeling and variable ordering

Several predicates are provided for choosing variables and assigning values to variables.

• indomain(V): V is instantiated to a value in the domain. On backtracking, the domain variable is instantiated to the next value in the domain.  

• deleteff(V,Vars,Rest): Chooses first a domain variable V from Vars with the minimum domain. Rest is a list of domain variables without V.  

• deleteffc(V,Vars,Rest): Chooses first a variable that has the smallest domain and that participates in the largest number of constraints.  

• labeling(Vars):
• fd_labeling(Vars): Label the variables in Vars one by one.  

• labeling_ff(Vars):
• labelingff(Vars):
• fd_labeling_ff(Vars): Label the variables in Vars by selecting first a variable with the smallest domain. If there are multiple variables with the same smallest domain, then the left-most one is chosen.    

• labeling_ff_min(Vars): The same as labeling_ff(Vars) but ties are broken by selecting a variable with the smallest lower bound.  

• labeling_ff_max(Vars): The same as labeling_ff(Vars) but ties are broken by selecting a variable with the largest upper bound.  

• labeling_ffc(Vars):
• labelingffc(Vars):
• fd_labeling_ffc(Vars): Label the variables in Vars by using deleteffc/3 to choose variables.    

• labeling_min(Vars): Label the variables in Vars by selecting first a variable with the smallest lower bound, breaking ties by selecting a variable with the smallest domain.  

• labeling_max(Vars): Label the variables in Vars by selecting first a variable with the largest upper bound, breaking ties by selecting a variable with the smallest domain.  

• labeling(Options,Vars):   Label the variables Vars under control by the list of search options, where Options may contain the following:
  • leftmost: The same as labeling(Vars).
  • forward: The same as labeling(Vars).
  • backward: The list of variables is reversed first before calling labeling.
  • inout: The variables are reordered in an inside-out fashion before calling labeling. For example, the variable list [X1,X2,X3,X4,X5] is rearranged into the list [X3,X2,X4,X1,X5].

  • min: Select first a variable whose domain has the smallest lower bound, breaking ties by selecting a variable with the smallest domain.
  • max: Select first a variable whose domain has the largest upper bound, breaking ties by selecting a variable with the smallest domain.

  • ff: The first-fail principle is used: the leftmost variable with the smallest domain is selected.
  • ff_forward: The same as ff.
  • ff_backward: The variables are reversed first before applying ff.
  • ff_inout: The variables are reordered in an inside-out fashion before applying ff.

  • ff_min: Same as ff but ties are broken by selecting a variable with the smallest lower bound.
  • ff_max: Same as ff but ties are broken by selecting a variable with the largest upper bound.

  • ffc: The most constrained heuristic is used: a variable with the smallest domain is selected, breaking ties selecting the variable that has the most propagators suspended on it.
  • ffc_backward: The variables are first reversed before applying ffc.
  • ffc_inout: The variables are reordered in an inside-out fashion before before applying ffc.
  • minimize(Exp):
  • maximize(Exp): Uses a branch-and-bound algorithm to find an assignment that minimizes (maximizes) the expression Exp. Exp must become ground after the variables are labeled.

  • time_out(Time)
  • time_out(Time,Result): This option imposes a time limit on labeling the variables. With this option, the labeling(Options,Vars) is equivalent to time_out(labeling(Options1,Vars),Time,Result) where Options1 is the same as Options but with no time_out option.  

• labeling_mix(Vars,Time,Strategies,Result):   Label the variables Vars under the time limit Time using the given list of strategies Strategies where each strategy is one of the following:
  • forward: The same as labeling(Vars).
  • backward: The same as labeling([backward],Vars).
  • inout: The same as labeling([inout],Vars).
  • ff_forward: The same as labeling_ff(Vars).
  • ff_backward: Reverse Vars before calling labeling_ff.
  • ff_inout: Reorder Vars in an inside-out fashion before calling labeling_ff.
  • ffc_forward: The same as labeling_ff(Vars).
  • ffc_backward: Reverse Vars before calling labeling_ff.
  • ffc_inout: Reorder Vars in an inside-out fashion before calling labeling_ffc.
  • min: The same as labeling_min(Vars).
  • max: The same as labeling_max(Vars).
  • ff_min: The same as labeling_ff_min(Vars).
  • ff_max: The same as labeling_ff_max(Vars).
  Result is bound to the successful strategy if a solution is found or time_out if no solution is found within the time limit. The given time is allocated to different strategies as follows: For the list of untried strategies, the first strategy gets half of the time and the rest gets the other half of the time. So for the list of strategies [s1,s2,s3], s1 gets half of the time, and s2 and s3 each gets a quarter of the time.

• labeling_mix(Vars,Time,Result):   Defined as follows:

     labeling_mix(Vars,Time,Result):-
        labeling_strategies(Strategies),
        labeling_mix(Vars,Time,Strategies,Result).
  

  where labeling_strategies(Strategies) binds Strategies to

  [forward,backward,inout,ff_forward,ff_backward,ff_inout,
   ffc_forward,ffc_backward,ffc_inout,min,max,ff_min,ff_max]
  

   

• labeling_mix(Vars,Time):   Same as labeling_mix(Vars,Time,_).