Back to SYMPHONY Home Page
Branching takes place whenever either (1) both cut generation and column generation (if it is performed) have failed, (2) ``tailing off'' in the objective function value has been detected (if this option is selected), or (3) the user chooses to force branching. Branching can take place on cuts or variables and can be fully automated or fully controlled the user, as desired. Branching can result in as many children as the user desires, though two is typical. Once it is decided that branching will occur, the user must either select the list of candidates for strong branching (see below for the procedure) or allow the framework to do so automatically by using one of several built-in strategies, such as branching on the variable whose value is farthest from integrality. The number of candidates can depend on the level of the current node in the tree. For instance, it is usually best to expend more effort on branching near the top of the tree where it is more ``important''.
After the list of candidates is selected, each candidate is pre-solved, by performing a specified number of iterations of the dual simplex algorithm in each child that would result from branching on the candidate object. Based on the objective function values obtained in each of the potential children, the final branching object is selected, again either by the user or by built-in rule. When the branching object has been selected, the LP process sends a description of it to the tree manager, which creates the children and adds them to the list of candidate nodes. It is then up to the tree manager to specify which node the now-idle LP process should process next. That issue will be addressed in Section 5.3.1 below.