So far, we have discussed how to control the branching and cut generation of IloCplex branch & cut search. The remaining missing piece is the node selection strategy. The node selection strategy determines which of the active nodes in the tree IloCplex chooses when it selects the next node for processing. IloCplex has several built-in node selection strategies, selected through parameter NodeSel.

When using goal-controlled search, node evaluators are used to override the built-in node selection strategy. The process is as follows. You combine a goal with a node evaluator by calling method IloCplex::Goal::Apply() (IloCplex.apply()). This method returns a new goal that implements the same search strategy as the goal passed as the parameter, but adds the node evaluator to every node in the subtree defined by the goal. Therefore, nodes may have a list of evaluators attached to them.

When node evaluators are used, nodes are selected as follows:

• IloCplex starts to choose the node with the built-in strategy as a first candidate.
• Then IloCplex loops over all remaining active nodes and considers choosing them instead.
• If a node has the same evaluator attached to it as the current candidate, the evaluator is asked if this node should take precedence over the current candidate. If the response is positive, the node under investigation becomes the new candidate and the test against other nodes continues.

If a node has multiple evaluators attached, they are consulted in the order the evaluators have been applied. This occurs as follows:

• If the first evaluator prefers one node over the other, the preferred node is used as candidate and the next node is considered.
• If the first evaluator does not give preference to one node over the other, the second evaluator is considered, and so on.

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

Node evaluators are implemented as subclasses of class IloCplex::NodeEvaluatorI. 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 calling method

IloNum IloCplex::NodeEvaluatorI::evaluate();

in the case of C++, and for Java by calling method:

double IloCplex.NodeEvaluator.evaluate();

This method must be implemented by users who write their own node evaluators. In method evaluate(), the protected member functions of class IloCplex::NodeEvaluatorI (IloCplex.NodeEvaluator) can be called to query information about the node being evaluated. The method evaluate() must compute and return an evaluation 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 only happens 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. This behavior can be altered 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);

IloCplex calls this method of an evaluator attached to the current candidate if the node being compared also has the same evaluator attached. The first parameter 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 parameters. 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 implementing your own node evaluator. Method void 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 calling the methods of class IloCplex::NodeEvaluatorI (IloCplex.NodeEvaluator).

Finally, for C++ 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.

Example ilogoalex3.cpp shows how to use node evaluators to implement a node selection strategy that chooses the deepest active node in tree among those with maximal sum of integer infeasibilities. Example ilogoalex3.cpp can be found in the examples/src directory of your distribution. The equivalent Java version can be found as file Goalex3.java at the same location.

// -------------------------------------------------------------- -*- C++ -*- // File: examples/src/ilogoalex3.cpp // Version 8.1 // -------------------------------------------------------------------------- // Copyright (C) 1999-2002 by ILOG. // All Rights Reserved. // Permission is expressly granted to use this example in the // course of developing applications that use ILOG products. // -------------------------------------------------------------------------- // // ilogoalex3.cpp - Node selectors in goal search // // This is an extension of example ilogoalex1.cpp // It adds node evaluators to further control the // goal based search. The node evaluator chooses // the node that is deepest in the tree among those // with maximum sum of integer infeasibilities // #include <ilcplex/ilocplex.h> ILOSTLBEGIN static void usage (const char *progname); // Branch on var with largest objective coefficient // among those with largest infeasibility ILOCPLEXGOAL1(MyBranchGoal, IloNumVarArray, vars) { IloNumArray x; IloNumArray obj; IntegerFeasibilityArray feas; x = IloNumArray(getEnv()); obj = IloNumArray(getEnv()); feas = IntegerFeasibilityArray(getEnv()); getValues(x, vars); getObjCoefs(obj, vars); getFeasibilities(feas, vars); IloInt bestj = -1; IloNum maxinf = 0.0; IloNum maxobj = 0.0; IloInt cols = vars.getSize(); for (IloInt j = 0; j < cols; ++j) { if ( feas[j] == Infeasible ) { IloNum xj_inf = x[j] - IloFloor (x[j]); if ( xj_inf > 0.5 ) xj_inf = 1.0 - xj_inf; if ( xj_inf >= maxinf && (xj_inf > maxinf || IloAbs (obj[j]) >= maxobj) ) { bestj = j; maxinf = xj_inf; maxobj = IloAbs (obj[j]); } } } IloCplex::Goal res; if ( bestj >= 0 ) { res = AndGoal(OrGoal(vars[bestj] >= IloFloor(x[bestj])+1, vars[bestj] <= IloFloor(x[bestj])), this); } x.end(); obj.end(); feas.end(); return res; } // Depth first search node evaluator class DepthEvaluatorI : public IloCplex::NodeEvaluatorI { public: IloNum evaluate() const { return -getDepth(); } IloCplex::NodeEvaluatorI *duplicateEvaluator() { return new DepthEvaluatorI(); } }; IloCplex::NodeEvaluator DepthEvaluator() { return new DepthEvaluatorI(); } // integer infeasibility sum node evaluator class IISumEvaluatorI : public IloCplex::NodeEvaluatorI { public: IloNum evaluate() const { return -getInfeasibilitySum(); } IloCplex::NodeEvaluatorI *duplicateEvaluator() { return new IISumEvaluatorI(); } }; IloCplex::NodeEvaluator IISumEvaluator() { return new IISumEvaluatorI(); } int main (int argc, char **argv) { IloEnv env; try { IloModel model(env); IloCplex cplex(env); if ( argc != 2 ) { usage (argv[0]); throw(-1); } IloObjective obj; IloNumVarArray var(env); IloRangeArray rng(env); cplex.importModel(model, argv[1], obj, var, rng); cplex.extract(model); IloCplex::Goal iiSumGoal = IloCplex::Apply(cplex, MyBranchGoal(env, var), IISumEvaluator()); IloCplex::Goal depthGoal = IloCplex::Apply(cplex, iiSumGoal, DepthEvaluator()); cplex.solve(depthGoal); IloNumArray vals(env); cplex.getValues(vals, var); cout << "Solution status = " << cplex.getStatus() << endl; cout << "Solution value = " << cplex.getObjValue() << endl; cout << "Values = " << vals << endl; } catch (IloException& e) { cerr << "Concert exception caught: " << e << endl; } env.end(); return 0; } static void usage (const char *progname) { cerr << "Usage: " << progname << " filename" << endl; cerr << " where filename is a file with extension " << endl; cerr << " MPS, SAV, or LP (lower case is allowed)" << endl; cerr << " Exiting..." << endl; }

As this example is an extension of example ilogoalex1.cpp, we shall only concentrate on the differences. Also, we will discuss the example only in terms of the C++ version; the Java version has identical structure and design and differs only in syntax.

The first is the definition of class DepthEvaluatorI as a subclass of IloCplex::NodeEvaluatorI. It implement methods evaluate() and duplicateEvaluator(). Method evaluate() simply returns the negative depth value queried for the current node by calling method getDepth(). Since IloCplex by default chooses nodes with the lowest evaluation value, this evaluator will favor nodes deep in the tree. Method duplicateEvaluator() simply returns a copy of the invoking object by calling the (default) copy constructor. Along with the class, we also define function DepthEvaluator() which creates an instance of class DepthEvaluatorI and returns a handle to it.

Similarly, we define class IISumEvaluatorI and function IISumEvaluator(). The evaluate() method returns the negation of the sum of integer infeasibilities of the node being evaluated. This number is obtained by calling method getInfeasibilitySum(). Thus, this evaluator favors nodes with larger sums of integer infeasibilities.

This example uses the same search strategy as ilogoalex1.cpp, implemented in goal MyBranchGoal. However, it applies first the IISumEvaluator to select nodes with high integer infeasibility sum, to choose between nodes with the same integer infeasibility sum it applies the DepthEvaluator. Applying the IISumEvaluator is done with

IloCplex::Goal iiSumGoal = IloCplex::Apply(cplex, MyBranchGoal(env, var), IISumEvaluator());

The goal created by calling MyBranchGoal is merged with the evaluator created by calling IISumEvaluator into a new goal iiSumGoal. Similarly, the iiSumGoal is merged with the node evaluator created by calling DepthEvaluator into a new goal depthGoal:

IloCplex::Goal depthGoal = IloCplex::Apply(cplex, iiSumGoal, DepthEvaluator());

Thus, depthGoal represents a goal implementing the branching strategy defined by MyBranchGoal, but using IISumEvaluator as a primary node selection strategy and DepthEvaluator as a secondary node selection strategy for breaking ties. This goal is finally used for the branch & cut search by passing it to the solve() method.

Node evaluators are only active while the search is controlled by goals. That is, if the goal stack becomes empty at a node and IloCplex continues searching with its built-in search strategy, that search is no longer controlled by any node evaluator. In order to maintain control over the node selection strategy while using the IloCplex branch strategy, you can use the goal returned by method IloCplex::GoalI::BranchAsCplexGoal() (IloCplex.branchAsCplex()). A goal that follows the branching performed by IloCplex built-in strategy can be easily implemented as:

ILOCPLEXGOAL0(DefaultSearchGoal) { if ( !isIntegerFeasible() ) return AndGoal(BranchAsCplexGoal(getEnv()), this); return 0; }

Notice the test for integer feasibility. Without that test, we would create an endless loop because when an integer feasible solution has been found, BranchAsCplex goal does not change the node at all, and this would continue to be executed indefinitely.