ilog.cplex

Class IloCplex.BranchCallback

java.lang.Object

ilog.cplex.IloCplex.Callback

ilog.cplex.IloCplex.OptimizationCallback

ilog.cplex.IloCplex.MIPInfoCallback

ilog.cplex.IloCplex.MIPCallback

ilog.cplex.IloCplex.ControlCallback

ilog.cplex.IloCplex.BranchCallback

All Implemented Interfaces:

java.lang.Cloneable

Enclosing class:

IloCplex

public abstract static class IloCplex.BranchCallback
extends IloCplex.ControlCallback

Base class for user-written callbacks that control branching.

This is an advanced class.

Important:

Advanced classes typically demand a profound understanding of the algorithms used by CPLEX. Thus they incur a higher risk of incorrect behavior in your application, behavior that can be difficult to debug. Therefore, the team encourages you to consider carefully whether you can accomplish the same task by means of other classes instead.

This is the base class for user-written callbacks that control branching during the branch-and-cut search. This callback will be called prior to the creation of the children of the current node. It allows you to query how the invoking instance of IloCplex is about to create the children, and gives you the opportunity to override creation of this branch.

You can create one or two branches by calling one of the makeBranch methods once or twice. It is an error to call that method more than twice.

By calling method prune, you remove the current node from the search tree. In other words, no subnodes from the current node will be added to the search tree. Calling both prune and makeBranch in one invocation of a branch callback is an error and yields unspecified behavior.

If you call neither prune nor makeBranch, the instance of IloCplex proceeds with its own branching.

The constructor and methods of this class are protected to make sure that they are used only to derive a user-written callback class or to implement the main method in it.

The user must be careful when using this class. Pruning a valid node can prune the optimal solution. Also, choosing a different branching variable can result in placing an invalid bound on a variable.

In particular, the user must not branch on variables that are implied feasible, as defined in IloCplex.IntegerFeasibilityStatus. Implied feasible means that the variable has been presolved out. It will be feasible when all other integer variables are feasible. Branching on such variables can cut off feasible solutions.

If the user intends to branch on continuous variables, the user must disable dual presolve reductions. To disable dual presolve reductions, set the parameter to control primal and dual reduction type, IloCplex.Param.Preprocessing.Reduce, either to the value 1 (one) (that is, CPX_PREREDUCE_PRIMALONLY) or to the value 0 (zero) (that is, CPX_PREREDUCE_NOPRIMALORDUAL).

Also, if the user intends to branch on continuous variables, the user must turn off the linear reduction switch, IloCplex.Param.Preprocessing.Linear.

By design, the CPLEX branch callback calculates and provides the branching decisions that CPLEX would make in case the user does not create any branches in the callback. Depending on variable selection and other features of your model, the computation of these candidate branches can be time-consuming. Consequently, if you know that you will never use the branching candidates suggested by CPLEX, then you can save time by disabling such features as strong branching.

See Also:

IloCplex.ControlCallback

Nested Class Summary

Nested classes/interfaces inherited from class ilog.cplex.IloCplex.MIPCallback

IloCplex.MIPCallback.NodeData

Nested classes/interfaces inherited from class ilog.cplex.IloCplex.Callback

IloCplex.Callback.Context, IloCplex.Callback.Function

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	IloCplex.BranchCallback() Constructor for user-written branch callbacks.

Method Summary

Methods

Modifier and Type	Method and Description
protected double[]	getBranches(IloNumVar[][] vars, double[][] bounds, IloCplex.BranchDirection[][] dirs) Queries the branches CPLEX would create at the current node if not overridden by the invoking callback.
protected IloCplex.BranchType	getBranchType() Returns the type of branching CPLEX is going to do at the current node unless overridden by the invoking callback.
protected int	getNbranches() Returns the number of branches CPLEX is going to create at the current node unless overridden by the invoking callback.
protected boolean	isIntegerFeasible() Returns true if the current node solution is considered to be integer feasible and thus potentially eligible as a new incumbent, but not suitable for branching.
protected IloCplex.NodeId	makeBranch(IloNumVar[] vars, double[] bounds, IloCplex.BranchDirection[] dirs, double objestimate) Creates a child node for the current node with the specified estimated objective value by setting more restrictive bounds on the variables in the array passed as an argument.
protected IloCplex.NodeId	makeBranch(IloNumVar[] vars, double[] bounds, IloCplex.BranchDirection[] dirs, double objestimate, java.lang.Object data) Creates a child node for the current node with the estimated objective value and additional user data by specifying more restrictive bounds on the variables in the array passed as an argument.
protected IloCplex.NodeId	makeBranch(IloNumVar var, double bound, IloCplex.BranchDirection dir, double objestimate) Creates a child node for the current node with the estimated objective value by setting one more restrictive bound on the specified variable.
protected IloCplex.NodeId	makeBranch(IloNumVar var, double bound, IloCplex.BranchDirection dir, double objestimate, java.lang.Object data) Creates a child node for the current node with the estimated objective value and additional user data by setting one more restrictive bound on the variable passed as an argument.
protected IloCplex.NodeId	makeBranch(IloRange[] cuts, double objestimate) Creates a child node for the current node by adding constraints to restrict its feasible domain.
protected IloCplex.NodeId	makeBranch(IloRange[] cuts, double objestimate, java.lang.Object data) Creates a child node for the current node with the estimated objective value and user data by adding constraints to restrict its feasible domain.
protected IloCplex.NodeId	makeBranch(IloRange rng, double objestimate) Creates a child node for the current node with the estimated objective value by adding one range constraint to restrict its feasible domain.
protected IloCplex.NodeId	makeBranch(IloRange rng, double objestimate, java.lang.Object data) Creates a child node for the current node with the estimated objective value and user data by adding one range constraint to restrict its feasible domain.
protected IloCplex.NodeId	makeBranch(int i, java.lang.Object data) Creates a child node for the current node that is identical to the branch i that CPLEX is doing.
protected void	prune() Instructs branch-and-cut search not to create any child nodes for the current node.

Methods inherited from class ilog.cplex.IloCplex.ControlCallback

getDownPseudoCost, getFeasibilities, getFeasibilities, getFeasibility, getLB, getLBs, getLBs, getNodeData, getNodeId, getObjValue, getSlack, getSlacks, getSlacks, getSOSFeasibility, getSOSFeasibility, getUB, getUBs, getUBs, getUpPseudoCost, getValue, getValue, getValues, getValues, setNodeData

Methods inherited from class ilog.cplex.IloCplex.MIPCallback

getCurrentNodeDepth, getNodeDoubleInfo, getNodeIntInfo, getNodeLongInfo, getObjCoef, getObjCoefs, getObjCoefs

Methods inherited from class ilog.cplex.IloCplex.MIPInfoCallback

getBestObjValue, getCutoff, getDirection, getIncumbentObjValue, getIncumbentValue, getIncumbentValue, getIncumbentValues, getIncumbentValues, getMIPRelativeGap, getNcuts, getNiterations, getNiterations64, getNnodes, getNnodes64, getNremainingNodes, getNremainingNodes64, getPriority, getQuality, hasIncumbent

Methods inherited from class ilog.cplex.IloCplex.OptimizationCallback

getModel, getNcols, getNQCs, getNrows

Methods inherited from class ilog.cplex.IloCplex.Callback

abort, getCplexTime, getDetTime, getEndDetTime, getEndTime, getStartDetTime, getStartTime, main

Methods inherited from class java.lang.Object

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

Constructor Detail

IloCplex.BranchCallback

protected IloCplex.BranchCallback()

Constructor for user-written branch callbacks.

This constructor can be called only to construct objects of derived user-written callback classes, but not to construct BranchCallback objects directly.

Method Detail

getNbranches

protected int getNbranches()

Returns the number of branches CPLEX is going to create at the current node unless overridden by the invoking callback.

Returns:

The number of branches IloCplex is going to create at the current node.

getBranchType

protected IloCplex.BranchType getBranchType()

Returns the type of branching CPLEX is going to do at the current node unless overridden by the invoking callback.

Returns:

The type of branching CPLEX is going to do at the current node.

getBranches

protected double[] getBranches(IloNumVar[][] vars,
                   double[][] bounds,
                   IloCplex.BranchDirection[][] dirs)
                        throws IloException

Queries the branches CPLEX would create at the current node if not overridden by the invoking callback.

The returned branch will be performed if the callback does not call the method makeBranch or prune.

Throws:

IloException

Parameters:

vars - An array of length at least getNbranches of arrays. Upon completion, vars[i] will contain the list of variables whose bounds will be changed in child i of the current node.

bounds - An array of length at least getNbranches of arrays. Upon completion, bounds[i] will contain the list of new bounds used for child i. One bound of variable vars[i][j] will be set to bounds[i][j] for all possible pairs i, j.

dirs - An array of length at least getNbranches of arrays. Upon completion of this method dirs[i] will contain the list of branch directions used for child i. If dirs[i][j] is IloCplex.BranchDirection.Up the lower bound of variable vars[i][j] will be set to bounds[i][j] for all possible pairs i, j. Similarly, if dirs[i][j] is IloCplex.BranchDirection.Down the upper bound of variable vars[i][j] will be set to bounds[i][j] for all possible pairs i, j.

Returns:

An array of double values containing the node estimates for the branches.

isIntegerFeasible

protected boolean isIntegerFeasible()
                             throws IloException

Returns true if the current node solution is considered to be integer feasible and thus potentially eligible as a new incumbent, but not suitable for branching.

Note that in this case, getNbranches returns 0 (zero).

Throws:

IloException

Returns:

true if the current node solution is integer feasible.

makeBranch

protected IloCplex.NodeId makeBranch(IloNumVar[] vars,
                         double[] bounds,
                         IloCplex.BranchDirection[] dirs,
                         double objestimate)
                              throws IloException

Creates a child node for the current node with the specified estimated objective value by setting more restrictive bounds on the variables in the array passed as an argument.

This method or any of the other makeBranch methods can be called zero, one, or two times. Each time one of the makeBranch methods is called, a child node of the current node is created, thereby overriding the branch decision taken by the invoking IloCplex object. It is an error to call one of the makeBranch methods more than twice. If no makeBranch method is called and the method prune is not called as well, the search is continued with the branching decision taken by the invoking IloCplex object.

Each call specifies a branch; in other words, it instructs the invoking IloCplex optimizer to create a subnode from the current node and tells the optimizer how to do so. This method specifies new, tighter bounds for a set of variables. The argument objestimate provides an estimate of the resulting optimal objective value for the subnode specified by this branch. The invoking instance of IloCplex may use this estimate to select nodes to process. A poor estimate will not influence the correctness of the solution, but it may influence performance. Using the objective value of the current node is usually a safe choice.

Throws:

IloException

Parameters:

vars - The array of variables for which new bounds will be set in the branch.

bounds - The array of new bounds for the variables corresponding to the variables in vars.

dirs - The array of branching directions for the variables in vars. Setting dirs[j] to IloCplex.BranchDirection.Up specifies that the lower bound of variable vars[j] is to be set to bounds[j]. Setting dirs[j] to IloCplex.BranchDirection.Down specifies that the upper bound of variable vars[j] is to be set to bounds[j].

objestimate - An estimate of the objective value at the subnode specified by this branch.

Returns:

The IloCplex.NodeId of the created child node.

makeBranch

protected IloCplex.NodeId makeBranch(int i,
                         java.lang.Object data)
                              throws IloException

Creates a child node for the current node that is identical to the branch i that CPLEX is doing.

This method or any of the other makeBranch methods can be called zero, one, or two times. Each time one of the makeBranch methods is called, a child node of the current node is created, It is an error to call one of the makeBranch methods more than twice.

This method creates the branch that CPLEX would create for branch i. Simultaneously, this method attaches the user object data to the new child node. The same index i must not be used with more than one call of the function.

Throws:

IloException

Parameters:

i - The index of the CPLEX branch to replicate.

data - A user data object to associate with the new node being created.

Returns:

The IloCplex.NodeId of the created child node.

makeBranch

protected IloCplex.NodeId makeBranch(IloNumVar[] vars,
                         double[] bounds,
                         IloCplex.BranchDirection[] dirs,
                         double objestimate,
                         java.lang.Object data)
                              throws IloException

Creates a child node for the current node with the estimated objective value and additional user data by specifying more restrictive bounds on the variables in the array passed as an argument.

This method or any of the other makeBranch methods can be called zero, one, or two times. Each time one of the makeBranch methods is called, a child node of the current node is created, thereby overriding the branch decision taken by the invoking IloCplex object. It is an error to call one of the makeBranch methods more than twice. If no makeBranch method is called and the method prune is not called either, the search is continued with the branching decision taken by the invoking IloCplex object.

Each call specifies a branch; in other words, it instructs the invoking IloCplex optimizer to create a subnode from the current node and tells the optimizer how to do so. This method specifies new, tighter bounds for a set of variables. The argument objestimate provides an estimate of the resulting optimal objective value for the subnode specified by this branch. The invoking instance of IloCplex may use this estimate to select nodes to process. A poor estimate will not influence the correctness of the solution, but it may influence performance. Using the objective value of the current node is usually a safe choice.

Throws:

IloException

Parameters:

vars - The array of variables for which new bounds will be set in the branch.

bounds - The array of new bounds for the variables corresponding to the variables in vars.

dirs - The array of branching directions for the variables in vars. Setting dirs[j] to IloCplex.BranchDirection.Up specifies that the lower bound of variable vars[j] is to be set to bounds[j]. Setting dirs[j] to IloCplex.BranchDirection.Down specifies that the upper bound of variable vars[j] is to be set to bounds[j].

objestimate - An estimate of the objective value at the subnode specified by this branch.

data - A user object that will be assigned to the newly created node. This object can later be queried from other callbacks with the method getNodeData.

Returns:

The IloCplex.NodeId of the created child node.

makeBranch

protected IloCplex.NodeId makeBranch(IloNumVar var,
                         double bound,
                         IloCplex.BranchDirection dir,
                         double objestimate)
                              throws IloException

Creates a child node for the current node with the estimated objective value by setting one more restrictive bound on the specified variable.

This method or any of the other makeBranch methods can be called zero, one or two times. Each time one of the makeBranch methods is called a child node of the current node is created, thereby overriding the branch decision taken by the invoking IloCplex object. It is an error to call one of the makeBranch methods more than twice. If no makeBranch method is called and the method prune is not called as well, the search is continued with the branching decision taken by the invoking IloCplex object.

Each call specifies a branch; in other words, it instructs the invoking optimizer how to create a subnode from the current node. In this method, this task is done by specifying a new, tighter bound for one variable.

The argument objestimate provides an estimate of the resulting optimal objective value for the subnode specified by this branch. The invoking instance of IloCplex may use this estimate to select nodes to process. A poor estimate will not influence the correctness of the solution, but it may influence performance. Using the objective value of the current node is usually a safe choice.

Throws:

IloException

Parameters:

var - The variable for which a new bounds will be set in the branch.

bound - The new bound for the variable var.

dir - The branching direction for var. Setting dir to IloCplex.BranchDirection.Up specifies that the lower bound of variable var is to be set to bound. Setting dir to IloCplex.BranchDirection.Down specifies that the upper bound of variable var is to be set to bound.

objestimate - An estimate of the objective value at the subnode specified by this branch.

Returns:

The IloCplex.NodeId of the created child node.

makeBranch

protected IloCplex.NodeId makeBranch(IloNumVar var,
                         double bound,
                         IloCplex.BranchDirection dir,
                         double objestimate,
                         java.lang.Object data)
                              throws IloException

Creates a child node for the current node with the estimated objective value and additional user data by setting one more restrictive bound on the variable passed as an argument.

This method or any of the other makeBranch methods can be called zero, one or two times. Each time one of the makeBranch methods is called a child node of the current node is created, thereby overriding the branch decision taken by the invoking IloCplex object. It is an error to call one of the makeBranch methods more than twice. If no makeBranch method is called and the method prune is not called as well, the search is continued with the branching decision taken by the invoking IloCplex object.

Each call specifies a branch; in other words, it instructs the invoking IloCplex optimizer to create a subnode from the current node and tells the optimizer how to do so. This method specifies a new, tighter bound for one variable.

The argument objestimate provides an estimate of the resulting optimal objective value for the subnode specified by this branch. The invoking instance of IloCplex may use this estimate to select nodes to process. A poor estimate will not influence the correctness of the solution, but it may influence performance. Using the objective value of the current node is usually a safe choice.

Throws:

IloException

Parameters:

var - The variable for which a new bounds will be set in the branch.

bound - The new bound for the variable var.

dir - The branching direction for var. Setting dir to IloCplex.BranchDirection.Up specifies that the lower bound of variable var is to be set to bound. Setting dir to IloCplex.BranchDirection.Down specifies that the upper bound of variable var is to be set to bound.

objestimate - An estimate of the objective value at the subnode specified by this branch.

data - A user object that will be assigned to the newly created node. This object can later be queried from other callbacks with the method getNodeData.

Returns:

The IloCplex.NodeId of the created child node.

makeBranch

protected IloCplex.NodeId makeBranch(IloRange[] cuts,
                         double objestimate)
                              throws IloException

Creates a child node for the current node by adding constraints to restrict its feasible domain.

This method or any of the other makeBranch methods can be called zero, one, or two times. Each time one of the makeBranch methods is called, a child node of the current node is created, thereby overriding the branch decision taken by the invoking IloCplex object. It is an error to call one of the makeBranch methods more than twice. If no makeBranch method is called and the method prune is not called as well, the search is continued with the branching decision taken by the invoking IloCplex object.

Each call specifies a branch; in other words, it instructs the invoking optimizer to create a subnode from the current node and tells the optimizer how to do so. This method specifies additional constraints that are added to the current node in order to define the child node.

The argument objestimate provides an estimate of the resulting optimal objective value for the subnode specified by this branch. The invoking optimizer may use this estimate to select nodes to process. A poor estimate will not influence the correctness of the solution, but it may influence performance. Using the objective value of the current node is usually a safe choice.

Throws:

IloException

Parameters:

cuts - The array of constraints that will be added to the current node in order to define the child node. All constraints must be linear.

objestimate - An estimate of the objective value at the subnode specified by this branch.

Returns:

The IloCplex.NodeId of the created child node.

makeBranch

protected IloCplex.NodeId makeBranch(IloRange[] cuts,
                         double objestimate,
                         java.lang.Object data)
                              throws IloException

Creates a child node for the current node with the estimated objective value and user data by adding constraints to restrict its feasible domain.

This method or any of the other makeBranch methods can be called zero, one, or two times. Each time one of the makeBranch methods is called, a child node of the current node is created, thereby overriding the branch decision taken by the invoking object. It is an error to call one of the makeBranch methods more than twice. If no makeBranch method is called and the method prune is not called as well, the search is continued with the branching decision taken by the invoking object.

Each call specifies a branch; in other words, it instructs the invoking optimizer to create a subnode from the current node and tells the optimizer how to do so. This method specifies additional constraints that will be added to the current node in order to define the child node.

The argument objestimate provides an estimate of the resulting optimal objective value for the subnode specified by this branch. The invoking optimizer may use this estimate to select nodes to process. A poor estimate will not influence the correctness of the solution, but it may influence performance. Using the objective value of the current node is usually a safe choice.

Throws:

IloException

Parameters:

cuts - The array of constraints that will be added to the current node in order to define the child node. All constraints must be linear.

objestimate - An estimate of the objective value at the subnode specified by this branch.

data - A user object that will be assigned to the newly created node. This object can later be queried from other callbacks with the method getNodeData.

Returns:

The IloCplex.NodeId of the created child node.

makeBranch

protected IloCplex.NodeId makeBranch(IloRange rng,
                         double objestimate)
                              throws IloException

Creates a child node for the current node with the estimated objective value by adding one range constraint to restrict its feasible domain.

This method or any of the other makeBranch methods can be called zero, one, or two times. Each time one of the makeBranch methods is called, a child node of the current node is created, thereby overriding the branch decision taken by the invoking object. It is an error to call one of the makeBranch methods more than twice. If no makeBranch method is called and the method prune is not called as well, the search is continued with the branching decision taken by the invoking object.

Each call specifies a branch; in other words, it instructs the invoking optimizer to create a subnode from the current node and tells the optimizer how to do so. This method specifies an additional constraint that needs to be added to the current node in order to define the child node.

The argument objestimate provides an estimate of the resulting optimal objective value for the subnode specified by this branch. The invoking optimizer may use this estimate to select nodes to process. A poor estimate will not influence the correctness of the solution, but it may influence performance. Using the objective value of the current node is usually a safe choice.

Throws:

IloException

Parameters:

rng - The constraint that will be added to the current node in order to define the child node. The constraint must be linear.

objestimate - An estimate of the objective value at the subnode specified by this branch.

Returns:

The IloCplex.NodeId of the created child node.

makeBranch

protected IloCplex.NodeId makeBranch(IloRange rng,
                         double objestimate,
                         java.lang.Object data)
                              throws IloException

Creates a child node for the current node with the estimated objective value and user data by adding one range constraint to restrict its feasible domain.

This method or any of the other makeBranch methods can be called zero, one, or two times. Each time one of the makeBranch methods is called, a child node of the current node is created, thereby overriding the branch decision taken by the invoking object. It is an error to call one of the makeBranch methods more than twice. If no makeBranch method is called and the method prune is not called as well, the search is continued with the branching decision taken by the invoking object.

Each call specifies a branch; in other words, it instructs the invoking optimizer to create a subnode from the current node and tells the optimizer how to do so. This method specifies an additional constraint that will be added to the current node in order to define the child node.

The argument objestimate provides an estimate of the resulting optimal objective value for the subnode specified by this branch. The invoking optimizer may use this estimate to select nodes to process. A poor estimate will not influence the correctness of the solution, but it may influence performance. Using the objective value of the current node is usually a safe choice.

Throws:

IloException

Parameters:

rng - The constraint that will be added to the current node in order to define the child node. The constraint must be linear.

objestimate - An estimate of the objective value at the subnode specified by this branch.

data - A user object that will be assigned to the newly created node. This object can later be queried from other callbacks with the method getNodeData.

Returns:

The IloCplex.NodeId of the created child node.

prune

protected void prune()

Instructs branch-and-cut search not to create any child nodes for the current node.

In short, if this method is called, CPLEX creates no branches at the current node. It is an error to call methods prune and makeBranch in one invocation of a branch callback.

Pruning nodes is not compatible with the method IloCplex.populate because that method retains fathomed nodes for subsequent use.