ILOG CPLEX 11.0 User's Manual > Advanced Programming Techniques > Using Goals > Example: Using Node Evaluators in a Node Selection Strategy |
Example: Using Node Evaluators in a Node Selection Strategy |
INDEX PREVIOUS NEXT |
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 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 ILOG 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 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 ILOG 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 ILOG CPLEX branch strategy, you can use the goal returned by the method IloCplex::GoalI::BranchAsCplexGoal
(IloCplex.branchAsCplex
). 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, BranchAsCplex
goal does not change the node at all, and this
would continue to be executed indefinitely.
Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |