Predefined search strategies

With Xpress Kalis a branching strategy is composed of three components:

• The branching scheme determines the shape of the search tree, this includes exhaustive schemes like assign_var and split_domain (enumeration of decision variables), settle_disjunction (enumeration over constraints), and task_serialize (enumeration of tasks in scheduling problems), or potentially incomplete searches with probe_assign_var or probe_settle_disjunction.
• The variable selection strategy determines the choice of the branching variables. Predefined selection criteria include

  KALIS_INPUT_ORDER

  variables in the given order,

  KALIS_LARGEST_MAX

  variable with largest upper bound,

  KALIS_LARGEST_MIN

  variable with largest lower bound,

  KALIS_MAX_DEGREE

  variable occurring in the largest number of constraints,

  KALIS_MAXREGRET_LB

  variable with largest difference between its lower bound and second-smallest domain value,

  KALIS_MAXREGRET_UB

  variable with largest difference between its upper bound and second-largest domain value,

  KALIS_RANDOM_VARIABLE

  random variable choice,

  KALIS_SDOMDEG_RATIO

  variable with smallest ratio domain size / degree,

  KALIS_SMALLEST_DOMAIN

  variable with smallest number of domain values/smallest domainintervall,

  KALIS_SMALLEST_MAX

  variable with smallest upper bound,

  KALIS_SMALLEST_MIN

  variable with smallest lower bound).

  KALIS_WIDEST_DOMAIN

  variable with largest number of domain values/largest domain interval,

  The user may also define his own variable selection strategy (see Section User search below).
• The value selection strategy determines the choice of the branching value once the variable to be branched on is known. The following predefined selection criteria are available.
  

  KALIS_MAX_TO_MIN

  enumeration of values in decreasing order,

  KALIS_MIDDLE_VALUE

  enumerate first values in the middle of the variable's domain,

  KALIS_MIN_TO_MAX

  enumeration of values in increasing order,

  KALIS_NEAREST_VALUE

  choose the value closest to a target value previously specified with settarget,

  KALIS_RANDOM_VALUE

  choose a random value out of the variable's domain.

  The predefined criteria can be replaced by the user's own value selection strategy (see Section User search below).

Depending on the choice of the branching scheme, it may be possible to specify additional parameters to configure the enumeration. The reader is referred to the Xpress Kalis reference manual for further detail. In the case of constraint branching, there is quite obviously no variable or branching value selection. The special case of task-based branching strategies (branching scheme task_serialize) is discussed in Section Enumeration. Enumeration of continuous variables (type cpfloatvar) always uses the branching scheme split_domain with the KALIS_SMALLEST_DOMAIN or KALIS_WIDEST_DOMAIN variable selection (the former is used by the default strategy, the latter often works better in purely continuous problems) and only a subset of the value selection strategies listed above.

Branching strategies may be defined for certain specified variables (or, where applicable, constraints or tasks), or, if the corresponding argument of the branching scheme function is left out, are applied to all decision variables in a model (see, for instance, model b4seq_ka.mos in Section element: Sequencing jobs on a single machine).

If the user's model does not specify any branching strategy, then Xpress Kalis will apply default strategies to enumerate all variables in the model. Even if one does not wish to change the default enumeration (for discrete variables: `smallest domain first' and `smallest value first'), it may still be desirable to define a branching strategy to fix a certain order for the enumeration of different groups of decision variables. The previous chapter contains several examples of this: in the model a4sugar_ka.mos (Section occurrence: Sugar production) we define an enumeration over some of the variables of a model, giving them thus preference over the remainder. In model j5tax_ka.mos (Section equiv: Location of income tax offices) we have seen an example of a search strategy composed of different enumerations for groups of decision variables.

If a model contains both, discrete and continuous variables (cpvar and cpfloatvar) the default strategies enumerate first the discrete and then the continuous variables.