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.
These conditions also mean that as soon as the goal stack
becomes empty and IloCplex proceeds with
built-in search strategies, the node
selection control by means of node evaluators is deactivated,
and the built-in strategy controlled by the parameter
IloCplex.IntParam.NodeSel is
used instead. In order for you to maintain control
over the node selection by means of
node evaluators while using the IloCplex branch strategy,
you can use a goal such as this one:
class DefaultSearchGoal extends IloCplex.Goal {
public IloCplex.Goal execute(IloCplex cplex) throws IloException {
if (!isIntegerFeasible())
return cplex.and(cplex.branchAsCplex(), this);
return null;
}
}
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 following goal
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.
cplex.or(cplex.apply(goal1, eval1),
cplex.apply(goal2, eval2));
To understand better 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
the 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.
| Modifier | Constructor and Description |
|---|---|
protected |
IloCplex.NodeEvaluator()
Constructor for user-written node evaluator.
|
| Modifier and Type | Method and Description |
|---|---|
protected abstract double |
evaluate()
Executes the invoking node evaluator.
|
protected 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.
|
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 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()
Initializes a node evaluator.
|
protected boolean |
subsume(double evalNode,
double evalCurrent)
Subsumes the invoking node evaluator.
|
protected IloCplex.NodeEvaluator()
This constructor can be called only to construct objects of
derived user-written callback classes, but not to construct
IloCplex.NodeEvaluator objects directly.
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 at which the evaluator has been initialized is referred to as the current node.
By returning Double.MAX_VALUE in this function, you
instruct IloCplex to prune the current node.
IloExceptionprotected boolean subsume(double evalNode,
double evalCurrent)
When it is 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.
evalNode - The evaluation value of the actual best candidate
node.evalCurrent - The evaluation value of the node being considered to
replace the actual candidate.true)
or the current tested node should replace it
(false).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 generally
makes it 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.
protected final double getObjValue()
throws IloException
This method can be called only from the methods
init and evaluate.
IloExceptionprotected final double getEstimatedObjValue()
throws IloException
This method can be called only from the methods
init and evaluate.
IloExceptionprotected final int getDepth()
throws IloException
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.
IloExceptionprotected final double getInfeasibilitySum()
throws IloException
This method can be called only from the methods
init and evaluate.
IloExceptionprotected final int getNinfeasibilities()
throws IloException
This method can be called only from the methods
init and evaluate.
IloExceptionprotected final IloNumVar getBranchVar() throws IloException
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.
IloExceptionprotected final int getLeftDepth()
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 arguments,
this call 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.
protected final int getRightDepth()
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 arguments,
this call 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.