ilog.cplex
Class IloCplex.SearchLimit

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

All Implemented Interfaces:

java.lang.Cloneable

Enclosing class:

IloCplex

public abstract static class IloCplex.SearchLimit

extends java.lang.Object

implements java.lang.Cloneable

This class allows you to limit the branch-and-cut search within certain subtrees. For example, you may consider doing so in order to limit the number of branches or nodes to use when exploring a certain decision. Such search limits can be implemented in the context of IloCplex goals by means of IloCplex.SearchLimit objects.

To create your own search limit, you must subclass IloCplex.SearchLimit and implement the method check. You may optionally implement the method init. Also, if the default implementation of method clone is not adequate and the goal is to be used for parallel optimization, this method needs also 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.

Prior to calling the methods check or init, IloCplex initializes the search limit object as the node for which to determine whether a search limit has been encountered. This node is referred to as the current node.

The method check must be implemented in such a way that it returns true if the limit has been reached and false otherwise. Information about the current node can be queried through the protected API of the class IloCplex.SearchLimit.

Before the method check is called for the first time, the virtual method init is called at that node. This method is called only once and allows you to initialize the search limit. As for the method check, information about the current node can be queried through the protected API of class IloCplex.SearchLimit.

The method IloCplex.limitSearch is used to create a goal that imposes a limit on a search controlled by a goal, as shown in this example:

    IloCplex.Goal limitGoal = cplex.limitSearch(goal1, limit);
  

In this example limit is of type IloCplex.SearchLimit and goal1 is of type IloCplex.Goal. The method IloCplex.limitSearch creates and returns a new goal that performs branch-and-cut search as specified by goal1 until the limit specified by limit is reached. In doing so, the search limit defined by limit is active only for the search subtree generated by goal1. For example, if you created two branches with the goal

    cplex.or(limitGoal, goal2);
  

only the subtree defined by goal1 is subjected to the search limit limit, while the subtree defined by goal2 is not.

The possibility of specifying search limits for subtrees leads to the possible situation where certain branches are subject to more than one search limit. Nodes with multiple search limits attached to them are processed only if none of the search limits has been reached, or, in other words, if all the search limits return false when the check method is called by IloCplex.

The fact that search limits are tied to goals implies that as soon as the goal stack becomes empty and IloCplex proceeds with built-in search strategies, the search limit is deactivated. In order to impose a search limit while using a built-in IloCplex branch strategy, a goal such as the following one can be used.

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

Constructor Summary

IloCplex.SearchLimit()
Creates a new search limit.

Method Summary

abstract boolean	check() This method must be implemented by the user.
int	getDepth() Returns the depth of the current node in the search tree.
int	getLeftDepth() Returns the left depth of the current node in the search tree.
int	getRightDepth() Returns the right depth of the current node in the search tree.
void	init() When a goal created with the method IloCplex.limitSearch is executed, IloCplex calls this method after initializing the invoked search limit to the current node.

Methods inherited from class java.lang.Object

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

Constructor Detail

IloCplex.SearchLimit

public IloCplex.SearchLimit()

Creates a new search limit.

Method Detail

check

public abstract boolean check()

This method must be implemented by the user. This method is called for the current node to check whether the limit implemented by the invoking search limit has been reached. If the limit has been reached, this virtual method should return true. If so, the unexplored subtree of the current node as well as the node itself will simply be discarded.

IloCplex initializes the search limit object to the node to be evaluated before calling method check. Information about this node can be queried through the protected API of class IloCplex.SearchLimit.

Returns:

A Boolean value indicating whether the limit has been reached.

init

public void init()

When a goal created with the method IloCplex.limitSearch is executed, IloCplex calls this method after initializing the invoked search limit to the current node. By overriding this method, users can initialize the search limit object.

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

getDepth

public final int getDepth()

Returns the depth of the current node in the search tree. 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 check.

Returns:

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

getLeftDepth

public 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.

When IloCplex.or is called with more than two parameters, this is 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 check.

Returns:

The left depth of the current node.

getRightDepth

public 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.

When IloCplex.or is called with more than two parameters, this is 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 check.

Returns:

The right depth of the current node.