Example: using node evaluators in a node selection strategy

Illustrates node evaluators in a node selection strategy.

The example ilogoalex3.cpp shows how to use node evaluators to implement a node selection strategy that chooses the deepest active node in the tree among those nodes with a maximal sum of integer infeasibilities. The example ilogoalex3.cpp can be found in the examples/src directory of your distribution. The equivalent Java implementation can be found in the file Goalex3.java at the same location. Likewise, the C#.NET example is available in Goalex3.cs.

As this example is an extension of the example ilogoalex1.cpp, this exposition of it concentrates only on their differences. Also, the example is discussed only in terms of the C++ implementation; the Java implementation has identical structure and design and differs only in syntax, as does the .NET as well.

The first difference is the definition of class DepthEvaluatorI as a subclass of IloCplex::NodeEvaluatorI. It implements the methods evaluate and duplicateEvaluator. The method evaluate simply returns the negative depth value queried for the current node by calling method getDepth. Since CPLEX 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 return 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 a high integer infeasibility sum; to choose between nodes with the same integer infeasibility sum, it applies the DepthEvaluator. Application of 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 in a new goal iiSumGoal. Similarly, the goal 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 CPLEX 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 CPLEX branch strategy, you can use the goal returned by the method IloCplex::GoalI::BranchAsCplexGoal (IloCplex.branchAsCplex or CplexBranchAsCplex). A goal that follows the branching performed by the built-in strategy of IloCplex 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, the goal BranchAsCplex does not change the node at all, and this would continue to be executed indefinitely.