Selectors are objects which select one object from a container of objects based on some selection criteria. In particular, selectors are used in Solver search goals to select the decision that will be taken at a search node. For example, a selector could be used to select which variable to explore or to select which value to assign to a given variable at a search node.

Selectors of objects of class Object from a container Container are instances of the template class IloSelector<Object,Container>.

For example, selectors of integer variables from an integer variable array are instances of IloSelector<IlcIntVar,IlcIntVarArray>.

A selector implements a function IloBool IloSelector<Object,Container>::select(Object& selected, Container c) that returns IloFalse if and only if no object could be selected and, otherwise, binds the variable selected given as the first argument to the selected object.

When the selector is used by a search goal, the member function select is called during the execution of the goal to perform the selection of the next decision.

Selectors can either be created on a Concert environment (IloEnv) or on the reversible heap of a solver (IloSolver) depending on the signature that is used to construct the selector.

There are two ways to define a selector:

• by hard coding the selection of an object using the ILOSELECTORi macros
• by using the predefined selector class IloBestSelector

When it is possible, IBM advises you to use the second approach as it is more flexible and modular.

The first way to define a selector is to use the ILOSELECTORi macros to define the selection code of a selector. Within the code of the macro, the user specifies which element Object of the given container of type Container is selected by invoking the select(Object) method.

For example, you could define a selector of integer variables from an integer variable array that selects a random variable in the array using the following code. This selector has one data field that stores a random generator.

ILOSELECTOR1(RandomVariableSelector,
             IlcIntVar,
             IlcIntVarArray, array,
             IloRandom, random) {
   select(array[random.getInt(array.getSize()-1)]); // Selected object
}

This macro defines the following two functions, which return a selector allocated either on a Concert environment (IloEnv) or on the reversible heap of a solver (IloSolver).

IloEnv env;
IloSolver solver = ...;
IloRandom random = ...;
IloSelector<IlcIntVar,IlcIntVarArray> sel1 = RandomVariableSelector(env, random);
IloSelector<IlcIntVar,IlcIntVarArray> sel2 = RandomVariableSelector(solver, random);

An instance of a variable can then be selected as follows:

IlcIntVarArray array = ...;
IlcIntVar selected;
IlcBool isSelected = sel2.select(selected, array);

The second way to define a selector is to use the predefined class IloBestSelector, which makes the best selection based on criteria that are supplied by parameters. There are many cases where, in order to select an object from a container, all the objects in the container need to be visited, filtered by a predicate, and then compared so that the best object from this comparison will be the selected one.

Such selectors are created using instances of IloBestSelector<Object,Container> which is a subclass of IloSelector<Object,Container>. This is a flexible and modular way to build a selector and IBM recommends that, when possible, you use this approach.

The IloBestSelector constructor can take up to three parameters:

• a visitor that allows you to specify how to visit the objects of an instance of container Container
• a predicate that allows you to filter objects from the container that cannot be selected
• a comparator that allows you to compare the candidate objects that have not been filtered and select the best among them

In addition, evaluators that evaluate an object and return an IloNum value can be used to build comparators. Translators, which translate objects of one type to another type, can be used to create both evaluators and predicates.

The concepts of visitor, predicate, comparator, evaluator, and translator are described in the following sections.

Visitors

A visitor IloVisitor<class Object,class Container> is a class that allows you to traverse each of the elements of type Object of a container class Container. For instance, a visitor can be used to specify how to traverse the set of variables IloIntVar of an array of variables IloIntVarArray.

Visitors can be created in three ways:

• by using the predefined default visitors in Solver
• by defining your own default visitor using the macro ILODEFAULTVISITOR
• by defining a new visitor using the ILOVISITORi macros

For a pair of classes <Object,Container>, you can define at most one visitor that will be considered as the default visitor for objects of type Object in container Container. By default, if no visitor is given at the construction of an instance of IloBestSelector<Object,Container>, the default visitor for the pair <Object,Container> will be used.

The following default visitors are predefined in Solver:

• <IloInt,IloIntArray>
• <IloNum,IloNumArray>
• <IloBool,IloBoolArray>
• <IloIntVar,IloIntVarArray>
• <IloNumVar,IloNumVarArray>
• <IloBoolVar,IloBoolVarArray>
• <IlcIntVar,IlcIntVarArray>
• <IlcFloatVar,IlcFloatVarArray>
• <IlcInt,IlcIntArray>
• <IlcFloat,IlcFloatArray>

These visitors traverse the elements of the arrays by increasing index from 0 until array.getSize()-1.

The macro ILODEFAULTVISITOR allows you to define a new default visitor for your own classes of objects and containers. Within the code of this macro, the function visit(Object) allows you to specify the visited objects.

For example, here is how the default visitor for integer variables in an integer variable array is defined in Solver:

ILODEFAULTVISITOR(IloIntVar,IloIntVarArray,array) {
   const IloInt size = array.getSize();
   for (IloInt i=0; i<size; ++i)
      visit(array[i]);
}

The ILOVISITORi macros allow you to define a new visitor with i data members.

For instance, the visitor defined in the following sample only visits the n first variables in an array of variables, n being a data field of the visitor:

ILOVISITOR1(VisitNFirst,
	    IlcIntVar,
            IlcIntVarArray, array,
            IlcInt, n) {
   const IloInt imax = IlcMin(n, array.getSize());
   for (IloInt i=0; i<imax; ++i)
      visit(array[i]);
}

An instance of such a visitor to visit the 10 first variables of an array can then be constructed as follows:

IloVisitor<IlcIntVar,IlcIntVarArray> visitor = VisitNFirst(solver, 10);

Predicates

A predicate on objects of type Object is a class that implements a test on an object and returns an IloBool value. Predicates on objects of type Object are instances of the template class IloPredicate<Object>.

Predicates are used in selectors to filter the set of candidate objects for selection.

The test function of a predicate is the member function IloBool operator()(Object obj, IloAny nu =0). This function returns IloTrue if and only if the object satisfies the predicate. An optional context nu can be passed to the test function in cases where the result of the test depends on some contextual information. When predicates are used in an instance of IloBestSelector<Object,Container>, the selector tests each visited object passing the instance of Container as context to the test function of the predicate.

Predicates can either be created on a Concert environment (IloEnv) or on the reversible heap of a solver (IloSolver) depending on the signature that is used to construct the predicate.

There are two ways to define a predicate:

• by defining a new predicate using the macros ILOPREDICATEi or ILOCTXPREDICATEi
• by composing existing predicates

The first way to create a predicate is to use the ILOPREDICATEi macros to define new predicates with i data members. The ILOCTXPREDICATEi macros define new predicates in the same way as the ILOPREDICATEi macros, except that you can add a context.

For example, the following code instantiates a predicate that tests whether or not an integer variable is bound:

ILOPREDICATE0(IsBound, 
              IlcIntVar, v) {
   return v.isBound(); 
}

The slightly more complex predicate that follows instantiates a predicate that tests whether an instance of IloIntVar is bound or not in a solver. The solver is stored as a data field of the predicate.

ILOPREDICATE1(IsBoundInSolver,
	      IloIntVar, v,
              IloSolver, solver) {
   return solver.isBound(v);
}

An instance of such a predicate can be allocated on a Concert environment as follows:

IloEnv env;
IloSolver solver1 = ...;
IloPredicate<IloIntVar> p1 = IsBoundInSolver(env, solver1);

Testing whether a given variable v is bound in solver solver1 can then be performed as follows:

IloIntVar v = ...;
IloBool   vIsBoundInSolver1 = p1(v);

The second way to create a predicate is to compose subordinate predicates using the logical operators !, &&, and || and the function IloIfThenElse.

For instance, if pi are predicates on objects of type <Object>, a composite predicate on objects of type <Object> can be defined as follows:

IloPredicate<Object> cp = IloIfThenElse(p0, p1&&!p2, p3) || p4;

Predicate cp will be true on an instance of object Object if and only if for that instance, p4 is true or, in case p0 is true, then p1 is true and p2 is false, otherwise (if p0 is false), p3 is true.

Predicates on objects of different types cannot be composed together. This will raise an error at compilation time.

Composite predicates, when invoked with a context, will pass this context to their subordinate predicates.

Comparators

A comparator is a class that implements a comparison between two objects. Comparators of objects of type Object are instances of the template class IloComparator<Object>.

Comparators are used in selectors to compare the candidate objects that have not been filtered and select the best among them.

There are two main comparison functions of a comparator: operator() and isBetterThan.

The function operator() takes two objects, o1 and o2, and by default returns -1, 0, or 1 depending on whether o1 is respectively better, equal or worse than o2. The optional argument nu is a context that can be used for the comparison:

IloInt operator()(IloObject o1, IloObject o2, IloAny nu = 0) const;

The function isBetterThan takes two objects, o1 and o2, and returns IloTrue if and only if o1 is preferred to o2. The optional argument nu is a context that can be used for the comparison:

IloBool isBetterThan(IloObject o1, IloObject o2, IloAny nu = 0) const;

Comparators can either be created on a Concert environment (IloEnv) or on the reversible heap of a solver (IloSolver) depending on the signature that is used to construct the comparator.

There are three ways to create comparators:

• by defining a new comparator using the ILOCOMPARATORi, ILOCTXCOMPARATORi, ILOCLIKECOMPARATORi, and ILOCTXCLIKECOMPARATORi macros
• by composing subordinate comparators using functions such as IloComposeLexical and IloComposePareto
• by using an evaluator to create a comparator

The first way to define a new comparator is to use macros to define the comparator. Comparators defined with ILOCOMPARATORi define a comparator with i data fields that must return a Boolean value equal to IloTrue if and only if the comparator's left-hand side is better than its right-hand side. The ILOCTXCOMPARATORi macros define new comparators in the same way, except that you can add a context for comparison.

For example, the following comparator compares the values of two IloNumVar variables in a solution. The solution is a context of the comparison.

ILOCTXCOMPARATOR0(HasValueSmallerThan,
                  IloIntVar, v1, v2,
                  IloSolution, sol) {
   return sol.getValue(v1) < sol.getValue(v2);
}

An instance of this comparator can be created as follows:

IloEnv env;
IloComparator<IloIntVar> comp = HasValueSmallerThan(env);

And it can be invoked as follows:

IloIntVar v1 = ...;
IloIntVar v2 = ...;
IloSolution sol = ...;
IloBool v1SmallerThanv2InSol = comp(v1,v2,&sol);

Comparators defined with ILOCLIKECOMPARATORi and ILOCTXCLIKECOMPARATORi are very similar to the ones defined by ILOCOMPARATORi and ILOCTXCOMPARATORi except for the return type of the comparison. The comparators defined by the ILOCLIKECOMPARATORi and ILOCTXCLIKECOMPARATORi macros return an integer equal to -1 if the comparator's left-hand side is better than its right-hand side, an integer equal to +1 if the comparator's right-hand side is better than its left-hand side, and an integer equal to 0 in cases where they are not comparable.

The second way to define a comparator is to compose subordinate comparators. The class IloCompositeComparator allows you to define a subclass of comparator that is composed of a list of subordinate comparators. New comparators can be added to this list by using the member function add.

Two of the most useful types of comparator composition are lexical composition and Pareto composition.

The following code defines a new comparator of objects of type Object as a lexical composition of n comparators.

IloLexicalComparator<Object> lc = IloComposeLexical(c1,c2,...,cn);

The composite comparator lc will prefer an object x to an object y if and only if there exists a comparator ci in the list of subordinate comparators such that:

• ci prefers x to y and
• all the previous comparators cj in the list (j<i) could not express any preference between x and y

The following code defines a new comparator of objects of type Object as a Pareto composition of n comparators.

IloComparator<Object> pc = IloComposePareto(c1,c2,...,cn);

The composite comparator pc will prefer an object x to an object y if and only if

• there is no comparator in the list of subordinate comparators that prefers y to x and
• there exists at least one comparator in the list of subordinate comparators that prefers x to y

The third way to define a comparator is very common. The first step is to define an evaluator that evaluates the objects and returns a numeric evaluation and then compare the objects depending on this evaluation by preferring the one with the lowest or greatest evaluation.

Evaluators and evaluator-based comparators are described in the next section.

Evaluators

An evaluator of objects of type Object is a class that implements an evaluation of an object and returns an IloNum value. Evaluators of objects of type Object are instances of the template class IloEvaluator<Object>.

The evaluation function of an evaluator is the member function IloNum operator()(Object obj, IloAny nu =0). This function returns an evaluation of the instance of the object given as an argument. An optional context nu can be passed to the evaluation function in cases where the result of the evaluation depends on some contextual information.

The member functions makeLessThanComparator and makeGreaterThanComparator are available on the evaluator base class IloEvaluator to build and return a comparator based on the invoking evaluator.

Evaluators can either be created on a Concert environment (IloEnv) or on the reversible heap of a solver (IloSolver) depending on the signature that is used to construct the evaluator.

There are two ways to define an evaluator:

• by defining a new evaluator using the ILOEVALUATORi and ILOCTXEVALUATORi macros
• by composing existing subordinate evaluators

The first way to create an evaluator is to use the ILOEVALUATORi macros to define new evaluators with i data members. The ILOCTXEVALUATORi macros define new evaluators in the same way as the ILOEVALUATORi macros, except that you can add a context.

For example, the following code instantiates an evaluator that returns the size of a variable's domain:

ILOEVALUATOR0(DomainSize, 
              IlcIntVar, v) {
   return v.getSize(); 
}

The slightly more complex evaluator in the following sample instantiates an evaluator that returns the value of an IloIntVar in a solution. The instance of the solution is passed as a context to the evaluation function.

ILOCTXEVALUATOR0(ValueInSolution,
	         IloIntVar, v,
                 IloSolution, sol) {
   return sol.getValue(v);
}

An instance of such an evaluator can be allocated on a Concert environment as follows:

IloEnv env;
IloEvaluator<IloIntVar> eval = ValueInSolution(env);

Evaluating a given variable v in the context of a given solution sol can then be performed as follows:

IloIntVar v = ...;
IloSolution sol = ...;
IloNum value = eval(v,&sol);

The second way to define an evaluator is to compose subordinate evaluators using algebraic operators such as +, -, *, /, IloMin, and IloMax and miscellaneous functions such as IloCeil or IloFloor.

For instance, if ei are evaluators on objects of type <Object>, a composite evaluator on objects of type <Object> can be defined as follows:

IloEvaluator<Object> ce = e1 * IloMin(e2 + IloFloor(3*e3), -e4)

Evaluators on objects of different types cannot be composed together. This will raise an error at compilation time.

Composite evaluators, when invoked with a context, will pass this context to their subordinate evaluators.

Composing evaluators and predicates

Evaluators can also be composed with predicates to build new evaluators. Likewise, predicates can be built as a composition of evaluators.

For example, the function IloIfThenElse allows you to instantiate a conditional evaluator that, depending on the test performed by a predicate p, will return the value of different evaluators (e1 if p is true, e2 otherwise):

IloEvaluator<Object> ce = IloIfThenElse(p, e1, e2);

Composite predicates can also be built as a composition of evaluators with the operators ==, !=, <, <=, >= and >.

For example, the following predicate will return IloTrue on an instance of Object, if and only if, for this instance, the evaluation of e1 is lower than the evaluation of e2:

IloPredicate<Object> p = (e1<e2);

Composite evaluators and predicates, when invoked with a context, will pass this context to their subordinate evaluators or predicates.

Translators

The template class IloTranslator<ObjectOut,ObjectIn> allows you to translate any object of type ObjectIn into a unique object of type ObjectOut.

Translators can be used to create both evaluators and predicates.

A translator IloTranslator<ObjectOut,ObjectIn> defines a translation member function that, given an input object o and an optional context, returns an output object that is the translation of the object passed as argument:

ObjectOut operator()(ObjectIn o, IloAny nu=0) 

Translators can be used to define new predicates and evaluators by using the composition operator <<.

Translators can either be created on a Concert environment (IloEnv) or on the reversible heap of a solver (IloSolver) depending on the signature that is used to construct the translator.

A new translator can be defined using the macro ILOTRANSLATOR.

For example, suppose an evaluator is available that returns the size of an instance of the Solver class IlcIntSet as defined in the following sample:

ILOEVALUATOR0(SetSize,
	      IlcIntSet, set) {
   return set.getSize();
}

Now suppose that you want to define an evaluator of an IlcIntSetVar that returns the size of its required set. You could write it explicitly as follows:

ILOEVALUATOR0(RequiredSetSize,
	      IlcIntSetVar, v) {
   return v.getRequiredSet().getSize();
}

An alternative is to define an object that automatically translates an instance of IlcIntSetVar into its unique required set and then compose this translator with the evaluator of IlcIntSet to build a new evaluator of IlcIntSetVar.

For instance in the above example, a translator that returns the required set of an IlcIntSetVar can be defined as follows:

ILOTRANSLATOR(RequiredSetTranslator,
              IlcIntSet,
              IlcIntSetVar, v) {
  return v.getRequiredSet();
}

The above translator that returns the required set of an IlcIntSetVar can then be composed with the evaluator of IlcIntSet to build a new evaluator of IlcIntSetVar:

IloEvaluator<IlcIntSet> sizeOfSet = SetSize(solver);
IloTranslator<IlcIntSet,IlcIntSetVar> requiredSet = RequiredSetTranslator(solver);
IloEvaluator<IlcIntSetVar> requiredSetSize = sizeOfSet << requiredSet;

Note that such composed evaluators and predicates, when invoked with a context, will pass this context to their subordinate evaluators/predicates and translators.

Example of a Selector

To demonstrate the concepts explained in this section, the following code sample gives a full example of a complex selector of IlcIntSetVar in an IlcIntSetVarArray that:

• will only consider the variables with an even index in the array (this is done with a new visitor)
• will only consider unbound variables with a non-empty required set (this is done with a predicate)
• will select an eligible variable with the smallest difference between the size of the possible set and the size of the required set, using the smallest size of possible set to break ties (this is done with a lexical comparator)

ILOVISITOR0(VarWithEvenIndex, 
	    IlcIntSetVar,
            IlcIntSetVarArray, array) {
   const IloInt size = array.getSize();
   for (IloInt i=0; i<size; i+=2)
      visit(array[i]);
}

ILOPREDICATE0(IsBound, 
              IlcIntSetVar, v) {
   return v.isBound(); 
}

ILOEVALUATOR0(SetSize,
	      IlcIntSet, set) {
   return set.getSize();
}

ILOTRANSLATOR(RequiredSetTranslator,
              IlcIntSet,
              IlcIntSetVar, v) {
  return v.getRequiredSet();
}

ILOTRANSLATOR(PossibleSetTranslator,
              IlcIntSet,
              IlcIntSetVar, v) {
  return v.getPossibleSet();
}

IloSolver s = ...;

IloEvaluator<IlcIntSetVar> sizeReq = SetSize(s) << RequiredSetTranslator(s);
IloEvaluator<IlcIntSetVar> sizePos = SetSize(s) << PossibleSetTranslator(s);

IloSelector<IlcIntSetVar,IlcIntSetVarArray> selector = 
  IloBestSelector(VarWithEvenIndex(s),
                  !IsBound(s) && (0 < sizeReq), 
                  IloComposeLexical((sizePos-sizeReq).makeLessThanComparator(), sizePos.makeLessThanComparator()));

See Also

IloBestSelector, IloComparator, IloCompositeComparator, IloEvaluator, IloLexicographicComparator, IloParetoComparator, IloPredicate, IloSelector, IloTranslator, IloVisitor, ILOCLIKECOMPARATOR0, ILOCOMPARATOR0, ILODEFAULTVISITOR, ILOEVALUATOR0, ILOPREDICATE0, ILOSELECTOR0, ILOTRANSLATOR, ILOVISITOR0, IloCeil, IloComposeLexical, IloComposePareto, IloFloor, IloIfThenElse, IloMax, IloMin.