next up previous contents index
Next: Branch-and-Bound Up: The Subproblem Previous: The Root Node of

The Other Nodes of the Branch-and-Bound Tree

As long as only globally valid constraints and variables are used it would be correct to initialize the constraint and variable system of a subproblem with the system of the previously processed subproblem. However, ABACUS\ is designed also for locally valid constraints and variables. Therefore, each subproblem inherits the final constraint and variable system of the father node in the enumeration tree. This system might be modified by the applied branching rule. Moreover, this approach avoids also tedious recomputations and makes sure that heuristically generated constraints do not get lost.

If conventional branching strategies, like setting a binary variable, changing the bounds of an integer variable, or even adding a branching constraint are applied, then the basis of the last solved linear program of the father is still dual feasible. As we store the basis status of the variables and slack variables we can avoid phase 1 of the simplex method if we use the dual simplex method.

If due to another branching method, e.g., for branch-and-price algorithms, the dual feasibility of the basis is lost, another LP-method can be used.



Stefan Thienel
Fri Sep 19 11:32:54 MET DST 1997