Search Tree

Having described the basics of how objects are represented, we now describe the representation of search tree nodes. Since the base constraints and variables are present in every subproblem, only the indices of the extra constraints and variables are stored in each node's description. A complete description of the current basis is maintained to allow a warm start to the computation in each search node. This basis is either inherited from the parent, computed during strong branching (see Section 4.4.2.3), or comes from earlier partial processing of the node itself (see Section 4.4.3.3). Along with the set of active objects, we must also store the identity of the object(s) which were branched upon to generate the node. The branching operation is described in Section 4.4.2.3.

Because the set of active objects and the status of the basis do not tend to change much from parent to child, all of these data are stored as differences with respect to the parent when that description is smaller than the explicit one. This method of storing the entire tree is highly memory-efficient. The list of nodes that are candidates for processing is stored in a heap ordered by a comparison function defined by the search strategy (see 4.4.3). This allows efficient generation of the next node to be processed.