Goals can be used to control the branch and cut search in IloCplex . Goals are implemented in the class IloCplex::GoalI . The class IloCplex::Goal is the handle class. That is, it contains a pointer to an instance of IloCplex::GoalI along with accessors of objects in the implementation class.

To implement your own goal, you need to subclass IloCplex::GoalI and implement its virtual member functions execute and duplicateGoal. The method execute controls the branch & cut search. The method duplicateGoal creates a copy of the invoking goal object to be used for parallel branch & cut search. Implementing your goal can be greatly simplified if you use one of the macros ILOCPLEXGOALn.

Every branch & cut node maintains a goal stack, possibly containing IloCplex::GoalI objects. After IloCplex solves the relaxation of a node, it pops the top goal from the goal stack and calls its method execute. There are several types of goals:

• If OrGoal is executed, IloCplex will create child nodes. Each of the child nodes will be initialized with a copy of the goal stack of the current node. Then, for each child node, the specified goal in the OrGoal is pushed onto the corresponding goal stack of the child node. Finally, the current node is deleted. (See IloCplex#GoalI::OrGoal for a more detailed discussion.)
• If a cut goal is executed, the constraint will be added to the current node relaxation. Constraint goals are provided to represent both local and global cuts. Local cut goals are conventionally used to express branching.
• If AndGoal is executed, its subgoals are simply pushed onto the stack. (See IloCplex::GoalI::AndGoal for a more detailed discussion.)
• If IloCplex::GoalI::FailGoal is executed, IloCplex will prune the current node; that is, it will discontinue the search at the current node. IloCplex will continue with another node if there is one still available in the tree.
• If IloCplex::GoalI::SolutionGoal is executed, IloCplex will attempt to inject a user-provided solution as a new incumbent. Before CPLEX accepts the injected solution, it first tests whether the injected solution is feasible with respect to the model and goals.
• When CPLEX executes any other goal, the returned goal is simply pushed onto the stack.

IloCplex continues popping goals from the goal stack until OrGoal or FailGoal is executed, or until the stack becomes empty; in the case of an empty stack, it will continue with a built-in search strategy.

The predefined goals OrGoal and AndGoal allow you to combine goals. AndGoal allows you to execute different goals at one node, while OrGoal allows you to execute different goals on different, newly created nodes. A conventional use of these two goals in a return statement of a user-written goal looks like this:

 
return AndGoal ( OrGoal (branch1, branch2), this);

This AndGoal first pushes this (the goal currently being executed) onto the goal stack, and then it pushes the OrGoal. Thus the OrGoal is on top of the stack and will be executed next. When the OrGoal executes, it creates two new nodes and copies the remaining goal stack to both of them. Thus both new nodes will have this goal on top of the goal stack at this point. Then the OrGoal proceeds to push branch1 onto the goal stack of the first child node and branch2 onto the goal stack of the second goal child node. Conventionally, branch1 and branch2 contain cut goals, so by executing branch1 and branch2 at the respective child nodes, the child nodes will be restricted to represent smaller subproblems than their parent. After branch1 and branch2 have been executed, this is on top of the node stack of both child nodes; that is, both child nodes will continue branching according to the same rule. In summary, this example creates the branches branch1 and branch2 and continues in both branches to control the same search strategy this.

To perform a search using a goal, you need to solve the extracted model by calling the method IloCplex::solve(goal) with the goal to use as an argument instead of the standard IloCplex::solve. The method solve(goal) simply pushes the goal onto the goal stack of the root node before calling the standard solve.

See Also

IloCplex::Goal and IloCplex::GoalI