ilog.cplex
Class IloCplex.NodeEvaluator

java.lang.Object
  |
  +--ilog.cplex.IloCplex.NodeEvaluator

All Implemented Interfaces:

java.lang.Cloneable

Enclosing class:

IloCplex

public abstract static class IloCplex.NodeEvaluator

extends java.lang.Object

implements java.lang.Cloneable

Node evaluators can be used to control the node selection strategy during the branch-and-cut search. When IloCplex finishes processing a node during branch-and-cut search it chooses a new active node from the tree to process. Node evaluators allow you to implement your own node selection strategy within any subtree controlled by goals.

Node evaluators are represented by objects of type IloCplex.NodeEvaluator. To create your own node evaluator, you must subclass class IloCplex.NodeEvaluator and implement the abstract method evaluate.

The evaluate method is called by IloCplex to compute a value for a given node. Given two nodes being evaluated by the same evaluator, by default IloCplex chooses the node with the lower value. However, this default behavior can be changed by overriding the method subsume.

If the default implementation of the method clone is not adequate and the goal is to be used for parallel optimization, this method also needs to be implemented by the user. Recall that the default clone method performs a shallow copy, so typically a user implementation would perform a deep copy for objects that should be local to threads or use the synchronize keyword where synchronization is required.

The method IloCplex.apply is used to impose a node selection strategy defined by a node evaluator on the search controlled by a goal, as shown in this example:

    IloCplex.Goal evalGoal = cplex.apply(goal, nodeEval);
  

In this example nodeEval is of type IloCplex.NodeEvaluator and goal is of type IloCplex.Goal. The method apply creates and returns a new goal that follows the node selection rule defined by nodeEval while performing branch-and-cut search as specified by goal. In doing so, the node selection strategy defined by nodeEval is active only for the search subtree generated by goal.

This also means that as soon as the goal stack becomes empty and IloCplex proceeds with built-in search strategies, the node selection control via node evaluators is deactivated, and the built-in strategy controlled by parameter IloCplex.IntParam.NodeSel is used instead. In order to maintain control over the node selection via node evaluators while using the IloCplex branch strategy, a goal such as:

       class DefaultSearchGoal extends IloCplex.Goal {
         public IloCplex.Goal execute(IloCplex cplex) throws IloException {
           if (!isIntegerFeasible())
             return cplex.and(cplex.branchAsCplex(), this);
           return null;
         }
       }
  

can be used.

An interesting implication of the correspondence between node evaluators and goals is that you can specify different node selection strategies for different subtrees. If goal1 and goal2 define the search in two subtrees of a branch-and-cut search tree, and eval1 and eval2 define two different node selection schemes, the goal

cplex.or(cplex.apply(goal1, eval1), cplex.apply(goal2, eval2));

will put the subtree defined by goal1 under the node selection strategy of eval1 and the subtree defined by goal2 under the node selection strategy of eval2.

To better understand how multiple node evaluators are handled, consider this additional information about the management of evaluators. When an evaluator is applied to a goal, the evaluator is attached to every node that will be created by that goal. This not only includes the nodes created by the execute method of the goal itself, but also those created by the goal returned by the execute method and so on. Since the execute method of a goal may create and return goals with other evaluators applied to them, every node may have a list of evaluators attached to it. The order of evaluators is the order in which the evaluators have been applied.

Each evaluator computes a value for every node it is attached to by calling the method evaluate. This method is called only once for a node and the result is stored. If a node evaluates to Double.MAX_VALUE (by means of an evaluator's method evaluate), the node is pruned from the tree, or, in other words, the node is removed from the tree along with the entire subtree that otherwise might have been generated from it.

When IloCplex chooses the next node to be processed it starts out with a candidate proposed by the built-in node selection strategy. There is a variety of such strategies that can be chosen with parameter IloCplex.IntParam.NodeSel.

After choosing an initial candidate node, IloCplex goes through the list of remaining nodes in the branch-and-cut tree to see if a node evaluator overrules this decision. Thus, for each active node IloCplex checks all the evaluators it has in common with the current candidate. By default, if a common evaluator computed a lower number for a node than for the current candidate, that node is used as a new candidate. However, by overriding the subsume method, a different overruling criterion can be implemented. The evaluators are checked in the order they are listed in the candidate node. This operation is repeated until all nodes have been checked. The candidate that survives this process will be chosen as the node to be processed for branch-and-cut search.

Constructor Summary

protected

IloCplex.NodeEvaluator() Constructor for user-written node evaluator.

Method Summary

protected abstract double	evaluate() IloCplex calls this method for every node controlled by the invoking evaluator in order to compute an evaluation value for the node.
protected ilog.concert.IloNumVar	getBranchVar() Returns the variable that was branched upon to create the current node.
protected int	getDepth() Returns the depth in the search tree of the current node.
protected double	getEstimatedObjValue() Returns the estimated objective value of the current node.
int	getId()
protected double	getInfeasibilitySum() Returns the sum of integer infeasibility of the current node.
protected int	getLeftDepth() Returns the left depth of the current node in the search tree.
protected int	getNinfeasibilities() Returns the number of integer infeasible variables for the current node.
protected IloCplex.NodeId	getNodeId() Returns the node identifier of the current node.
protected double	getObjValue() Returns the objective value of the current node.
protected int	getRightDepth() Returns the right depth of the current node in the search tree.
protected void	init() This method is called by IloCplex right before the first time evaluate is called for a node and allows you to initialize the evaluator based on that node.
protected boolean	subsume(double evalNode, double evalCurrent) When choosing the next node to be processed, IloCplex maintains a candidate node to pick.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

IloCplex.NodeEvaluator

protected IloCplex.NodeEvaluator()

Constructor for user-written node evaluator. This constructor can be called only to construct objects of derived user-written callback classes, but not to construct IloCplex.NodeEvaluator objects directly.

Method Detail

getId

public final int getId()

evaluate

protected abstract double evaluate()
                            throws IloException

IloCplex calls this method for every node controlled by the invoking evaluator in order to compute an evaluation value for the node. These values are then used to select the next node to be processed. Given two nodes controlled by one evaluator, by default, the evaluator chooses the node with the lower evaluation value. However, this can be changed by overriding the method subsume.

IloCplex calls the method evaluate only once for every node, and reuses the returned value for that node whenever comparing it with another node.

When this method is called, the evaluator has been initialized to the node to evaluated, such that the other methods of the invoking evaluator can be called to query information about this node. The node the evaluator has been initialized to is referred to as the current node.

By returning Double.MAX_VALUE in this function, you instruct IloCplex to prune the current node.

Returns:

The evaluation value of the current node.

IloException

subsume

protected boolean subsume(double evalNode,
                          double evalCurrent)

When choosing the next node to be processed, IloCplex maintains a candidate node to pick. Then it compares that candidate to all other active nodes. If a given node and the candidate node are governed by the same evaluator, IloCplex calls the method subsume to determine whether the node should become the new candidate. The arguments passed to the subsume call are the values the invoking evaluator previously assigned to the nodes under consideration with the method evaluate. By default, this method returns false if the evaluation value of the current node being tested is less than the evaluation of the candidate node. Overriding this function allows you to change this selection scheme.

Parameters:

evalNode - The evaluation value of the actual best candidate node.

evalCurrent - The evaluation value of the node being considered to replace the actual candidate.

Returns:

A Boolean value indicating whether the best candidate node should remain the same (true) or the current tested node should replace it (false).

init

protected void init()

This method is called by IloCplex right before the first time evaluate is called for a node and allows you to initialize the evaluator based on that node. Information about the node can be queried when this method is called.

The method init is called only once for an evaluator. This convention makes it generally impossible to use one evaluator object in two subtrees, because init would be called only in one subtree and thus the evaluator would not be correctly initialized for the other subtree. Use two separate instances of your evaluator instead to overcome this convention.

getNodeId

protected final IloCplex.NodeId getNodeId()
                                   throws IloException

Returns the node identifier of the current node. This method can be called only from the methods init and evaluate.

Returns:

The IloCplex.NodeId of the current node.

IloException

getObjValue

protected final double getObjValue()
                            throws IloException

Returns the objective value of the current node. This method can be called only from the methods init and evaluate.

Returns:

The objective value of the current node.

IloException

getEstimatedObjValue

protected final double getEstimatedObjValue()
                                     throws IloException

Returns the estimated objective value of the current node. This method can be called only from the methods init and evaluate.

Returns:

The estimated objective value of the current node.

IloException

getDepth

protected final int getDepth()
                      throws IloException

Returns the depth in the search tree of the current node. The root node is defined to have depth 0 (zero); the depth of other nodes is their distance from the root, or, equivalently, the number of branches taken to get from the root to that node. This method can be called only from the methods init and evaluate.

Returns:

The depth of the current node in the branch-and-cut tree.

IloException

getInfeasibilitySum

protected final double getInfeasibilitySum()
                                    throws IloException

Returns the sum of integer infeasibility of the current node. This method can be called only from the methods init and evaluate.

Returns:

The sum of integer infeasibility of the current node.

IloException

getNinfeasibilities

protected final int getNinfeasibilities()
                                 throws IloException

Returns the number of integer infeasible variables for the current node. This method can be called only from the methods init and evaluate.

Returns:

The number of integer infeasibilities for the current node.

IloException

getBranchVar

protected final ilog.concert.IloNumVar getBranchVar()
                                             throws IloException

Returns the variable that was branched upon to create the current node. If a more complex branch was used to create the current node null is returned instead. This method can be called only from the methods init and evaluate.

Returns:

The branch variable of the current node.

IloException

getLeftDepth

protected final int getLeftDepth()

Returns the left depth of the current node in the search tree. The root node is depth 0 (zero); the left depth of other nodes is the number of times that the first goal in a call to IloCplex.or has been taken when branching down from the root to the current node.

If IloCplex.or is called with more than two parameters, this is in fact translated into a sequence of or goals with two children each. For example, IloCplex.or(goal1, goal2, goal3); is internally translated into IloCplex.or(goal1, IloCplex.or(goal2, goal3)); to form a binary tree. This transformation is accounted for when defining the left depth of a node.

This method can be called only from the methods init and evaluate.

Returns:

The left depth of the current node.

getRightDepth

protected final int getRightDepth()

Returns the right depth of the current node in the search tree. The root node is depth 0 (zero); the right depth of other nodes is the number of times that the second goal in a call to IloCplex.or has been taken when branching down from the root to the current node.

If IloCplex.or is called with more than two parameters, this is in fact translated into a sequence of or goals with two children each. For example, IloCplex.or(goal1, goal2, goal3); is internally translated into IloCplex.or(goal1, IloCplex.or(goal2, goal3)); to form a binary tree. This transformation is accounted for when defining the right depth of a node.

This method can be called only from the methods init and evaluate.

Returns:

The right depth of the current node.