One critical point of B&B is the storing of the enumeration tree. When a branch is fathomed then even some of its ancestors can become completely fathomed provided that the current branch was the last unfathomed subbranch of the ancestors. The ancestors are stored also otherwise it is not possible to restore the successor. As B&B uses the enumeration tree on a flexible way, it can be necessary to store a large amount of information on branches. It can causes memory problems. On the other hand it would be too expensive from the point of view of calculations to check the ancestors every time if a branch becomes fathomed. This section gives some ideas how to make a trade-off.
The first thing is to decide is that which data are describing a branch. There are two options. The first one is that all necessary informations are stored for each branch. It includes all the branching defining constraints. In that case the same constraint is stored many times, because a branch on a higher level may have many subbranches. As matter of fact the number of branches is very high in the case of large scale problems, thus the memory required by this solution is very high.
The other option is that only those informations are stored which are necessary to the complete reconstruction of the branch. These ones are
the parent branch, i.e. the branch from which it was generated directly,
the bound of the objective function on the branch,
the index of the branching variable,
the branch defining constraint of the branching variable.
For technical reasons three other attributes are used as well:
a Boolean variable showing if the branch has been decomposed into subbranches,
another Boolean variable showing if any unfathomed subbranch of the branch exists,
and a pointer to the next element in the list of branches.
Thus a branch can be described by a record as follows:
BEGINParent : Branch; Bound :
INTEGER; Variable :
INTEGER; Value :
INTEGER; Decomposition :
BOOLEAN; Descendant :
BOOLEAN; suc : Branch
The value of the Parent attribute is none if and only if the branch is the initial branch, i.e. the complete problem. It is the root of the B&B tree. The reconstruction of the constraints defining the particular branch is the simplest if it is supposed that the branches are defined by the fixing of a free variable. Assume that Node is a variable of type Branch. At the beginning its value is the branch to be reconstructed. Then the algorithm of the reconstruction is as follows.
DO[Node.Variable] Node.Value; 3 4 Node Node.Parent; 5
The value of a previously fixed variable is set to the appropriate value in row 2. Further operations are possible (row 3). Node becomes its own parent branch in row 4. If it is none then the root is passed and all fixings are done.
Sometimes it is necessary to execute some operations on all elements of the list . The suc attribute of the branches point to the next element of the list. The last element has no next element, therefore the value of suc is none in this case. The procedure of changing all elements is somewhat similar to the
procedure. The head of the list is Tree, i.e. the first element of the list is Tree.suc.
1 Node Tree.suc 2
NONE3 4 Node Node.suc 5
The loop runs until there is no next element. The necessary operations are executed in row 3. The variable Node becomes the next element of the list in row 4. To insert a new branch into the list is easy. Assume that it is NewNode of type Branch and it is to be inserted after Node which is in the list. Then the necessary two commands are:
If the branches are not stored as objects but they are described in long arrays then the use of attribute suc is superflous and instead of the procedure
loop can be applied.
The greatest technical problem of B&B from computer science point of view is memory management. Because branches are created in enormous large quantity the fathomed branches must be deleted from the list time to time and the memory occupied by them must be freed. It is a kind of garbage collection. It can be done in three main steps. In the first one value false is assigned to the attribute Descendant of all elements of the list. In the second main step an attribute Descendant is changed to true if and only if the branch has unfathomed descendant(s). In the third step the unnecessary branches are deleted. It is assumed that there is a procedure Out which gets the branch to be deleted as a parameter and deletes it and frees the part of the memory.
1 Node Tree.suc 2
FALSE4 Node Node.suc 5 Node Tree.suc 6
DO/TTBF TTBFIF NOTNode.Decomposition
ANDNode.Bound ≥ 8
THENPont Node.Parent 9
NONE DO10 Pont.Descendant
TRUE11 Pont Pont.Parent 12 Node Node.suc 13 Node Tree.suc 14
NONE DO15 Pont Node.suc 16
AND/TTBF NODE.DECOMPOSITION) TTBFORNode.Bound 17
THENOut(Node) 18 Node Pont 19