So far, you have seen how to control the branching and cut generation of ILOG CPLEX branch & cut search. The remaining missing piece is the node selection strategy. The node selection strategy sets which of the active nodes in the tree ILOG CPLEX chooses when it selects the next node for processing. ILOG CPLEX has several built-in node selection strategies, selected through the parameter NodeSel (CPX_PARAM_NODESEL).

When you use goal-controlled search, you use node evaluators to override the built-in node selection strategy. You combine a goal with a node evaluator by calling the method IloCplex::Goal::Apply (IloCplex.apply or Cplex.Apply). This method returns a new goal that implements the same search strategy as the goal passed as the argument, but adds the node evaluator to every node in the subtree defined by the goal. Consequently, nodes may have a list of evaluators attached to them.

When node evaluators are used, nodes are selected like this:

If a node has multiple evaluators attached, they are consulted in the order the evaluators have been applied. Here is the application order:

Thus, by adding multiple evaluators, you can build composite node selection strategies where later evaluators are used for breaking ties in previous evaluations.

In the C++ API, node evaluators are implemented as subclasses of class IloCplex::NodeEvaluatorI. The class IloCplex::NodeEvaluator is the handle class for node evaluators.

In Java, node evaluators are implemented in objects of type IloCplex.NodeEvaluator (and there are no handle classes).

Like goals, node evaluators use reference counting for memory management. As a result, you should always use the handle objects when dealing with node evaluators, and there is no method end to be called.

Node evaluators use a two-step process to decide whether one node should take precedence over another. First, the evaluator computes a value for every node to which it is attached. This is done by the method evaluate in C++:

IloNum IloCplex::NodeEvaluatorI::evaluate();

and in Java, by the method:

double IloCplex.NodeEvaluator.evaluate();

and in C#.NET:

double Cplex.NodeEvaluator.Evaluate();

This method must be implemented by users who write their own node evaluators. In the method evaluate, the protected methods of the class IloCplex::NodeEvaluatorI (IloCplex.NodeEvaluator or Cplex.NodeEvaluator) can be called to query information about the node being evaluated. The method evaluate must compute and return an evaluation (that is, a value) that is used later on, in the second step, to compare two nodes and select one of them. The evaluate method is called only once for every node, and the result is cached and reused whenever the node is compared against another node with the evaluator.

The second step consists of comparing the current candidate to another node. This comparison happens only for evaluators that are shared by the current candidate and the other node. By default, the candidate is replaced by the other node if its evaluation value is smaller than that of the candidate. You can alter his behavior by overwriting the method

IloBool IloCplex::NodeEvaluatorI::subsume(IloNum candVal, IloNum nodeVal);

or, in the case of Java:

boolean IloCplex.NodeEvaluator.subsume(double candVal, double nodeVal);

or, in the case of C#.NET:

bool Cplex.NodeEvaluator.Subsume(double evalNode, double evalCurrent);

ILOG CPLEX calls this method of an evaluator attached to the current candidate if the node being compared also has the same evaluator attached. The first argument candVal is the evaluation value the evaluator has previously computed for the current candidate, and nodeVal is the evaluation value the evaluator has previously computed for the node being tested. If this method returns IloTrue (true), the candidate is replaced. Otherwise, the method is called again with reversed arguments. If it still returns IloFalse (false), both nodes are tied with respect to that evaluator, and the next evaluator they share is consulted. Otherwise, the current candidate is kept and tested against the next node.

There are two more virtual methods defined for node evaluators that should be considered when you implement your own node evaluator. The method init is called right before evaluate is called for the first time, thus allowing you to initialize internal data of the evaluator. When this happens, the evaluator has been initialized to the first node to be evaluated; thus information about this node can be queried by the methods of the class IloCplex::NodeEvaluatorI (IloCplex.NodeEvaluator).

Finally, in C++, the method

IloCplex::NodeEvaluatorI* IloCplex::NodeEvaluatorI::duplicateEvaluator();

must be implemented by the user to return a copy of the invoking node evaluator object. This method is called by IloCplex to create copies of the evaluator for parallel branch & cut search.