So far, you have seen 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 like this:

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

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 the method evaluate, the protected methods of the 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 (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 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. 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 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 9.0    
// --------------------------------------------------------------------------
//  Copyright (C) 1999-2003 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, it concentrates only on the differences. Also, the example is discussed 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 the methods evaluate and duplicateEvaluator. The 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. The method duplicateEvaluator simply returns a copy of the invoking object by calling the (default) copy constructor. Along with the class, the function DepthEvaluator is also defined to create an instance of class DepthEvaluatorI and returns a handle to it.

Similarly, the class IISumEvaluatorI and function IISumEvaluator are also defined. 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, the application 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.