The Goal Stack

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

When IloCplex 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. IloCplex keeps doing this until the node becomes inactive or the node's goal stack becomes empty. When the node stack is empty, IloCplex continues with its built-in search strategy for the subtree rooted at this node.

Let us now review the different types of goals in light of the goal stack:

  1. As we already discussed, the Or goal creates child nodes. IloCplex 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 parameter to the Or goal on the goal stack of the corresponding node. Finally, the current node is deactivated, and IloCplex continues search by picking a new active node from the tree to process.

  2. The And goal simply pushes the goals passed as parameters onto the goal stack in reverse order. Thus, when popping the goals from the stack for execution, they will be executed in the same order as they were passed as parameters to method And goal.

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

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

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

With this understanding, let us revisit 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 the Or goal. Thus, the Or goal is the next goal that IloCplex 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

(where

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

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

When IloCplex 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 we just saw, this will be a local cut goal. Thus IloCplex adds the constraint to the node problem and re-solves the relaxation. Next, this will be popped from the goal stack and executed. This means that the same search strategy as implemented in the original goal is applied at that node.

Copyright © 2002 ILOG
http://www.ilog.com
 
 
 
 
Previous Page: Goals in IloCplex Return to Top Next Page: Memory Management and Goals