The goal stack

Describes the goal stack.

To understand how goals are executed, consider the concept of the goal stack. Every node has its own goal stack. When cplex.solve(goal) is called, the goal stack of the root node is simply initialized with goal and then the regular cplex.solve method is called.

When CPLEX processes a node, it pops the first goal from the node's goal stack and calls method execute. If a nonempty goal is returned, it is simply pushed back on the stack. CPLEX keeps doing this until the node becomes inactive or the node's goal stack becomes empty. When the node stack is empty, CPLEX continues with its built-in search strategy for the subtree rooted at this node.

In light of the goal stack, here are the different types of goals:

  • As explained in Or goal, the Or goal creates child nodes. CPLEX first initializes the goal stack of every child node with a copy of the remaining goal stack of the current node. Then it pushes the goal passed as the argument to the Or goal on the goal stack of the corresponding node. Finally, the current node is deactivated, and CPLEX continues search by picking a new active node from the tree to process.

  • The And goal simply pushes the goals passed as arguments onto the goal stack in reverse order. Thus, when the goals are popped from the stack for execution, they will be executed in the same order as they were passed as arguments to the And goal.

  • When a Fail goal executes, the current node is simply deactivated, and CPLEX continues on another active node from the tree. In other words, CPLEX discontinues its search below the current node.

  • When a local cut goal is executed, its constraints are added to the node problem as local cuts and the relaxation is re-solved.

  • An empty goal cannot be executed. Thus, empty goals are not pushed onto the goal stack. If the goal stack is empty, CPLEX continues with the built-in branching strategy.

With this understanding, consider further what really goes on when a goal returns: 


return AndGoal(OrGoal(var <= IloFloor(val), var >= IloFloor(val)+1), this);

The And goal is pushed onto the current node's goal stack, only to be immediately popped back off of it. When it is executed, it will push this on the goal stack and then push the Or goal. Thus, the Or goal is the next goal that CPLEX pops and executes. The Or goal creates two subnodes, and initializes their goal stacks with copies of the goal stack of the current node. At this point both subnodes will have this on top of their goal stacks. Next, the Or goal will push a local cut goal for

goals7

(where

goals8

denotes the floor of val) on the goal stack of the first subnode. Similarly, it pushes a local cut goal for

var  ≥goals9

on the goal stack of the second subnode. Finally, the current node is deactivated and CPLEX continues its search with a new active node from the tree.

When CPLEX processes one of the subnodes that have been created by the Or goal, it will pop and execute the first goal from the node's goal stack. As you just saw, this will be a local cut goal. Thus CPLEX adds the constraint to the node problem and re-solves the relaxation. Next, this will be popped from the goal stack and executed. That fact means that the same search strategy as implemented in the original goal is applied at that node.