24.4. 24.4 On the enumeration tree

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

For technical reasons three other attributes are used as well:

Thus a branch can be described by a record as follows:

       
               
                  RECORD
                Branch       
                  BEGIN
                         Parent                                 : Branch;          Bound                                  : 
                  INTEGER
               ;          Variable                               : 
                  INTEGER
               ;          Value                                  : 
                  INTEGER
               ;          Decomposition                          : 
                  BOOLEAN
               ;          Descendant                             : 
                  BOOLEAN
               ;          suc                                    : Branch       
                  END
               ;

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.

Branch-Reconstruction

  1  
                  WHILE
                Node 
               
                  NONE
                  2    
                  DO
                
               [Node.Variable] Node.Value;   3          4       Node Node.Parent;   5  
                  RETURN
                Node 

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 Branch Reconstruction procedure. The head of the list is Tree, i.e. the first element of the list is Tree.suc.

B&B-List

  1  Node Tree.suc   2  
                  WHILE
                Node 
               
                  NONE
                  3       4    Node Node.suc   5  
                  RETURN
                Node 

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:

NewNode.suc Node.suc

           Node.suc NewNode

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 B&B List a for 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.

Garbage-Collection

  1  Node Tree.suc   2  
                  WHILE
                Node 
               
                  NONE
                  3    Node.Descendant 
               
                  FALSE
                  4    Node Node.suc   5  Node Tree.suc   6  
                  WHILE
                Node 
               
                  NONE
                  7    
                  DO/TTBF TTBFIF NOT
                Node.Decomposition 
                  AND
                Node.Bound ≥    8    
                  THEN
                Pont Node.Parent   9    
                  WHILE
                Pont 
               
                  NONE DO
                 10       Pont.Descendant 
               
                  TRUE
                 11       Pont Pont.Parent  12    Node Node.suc  13  Node Tree.suc  14  
                  WHILE
                Node 
               
                  NONE DO
                 15    Pont Node.suc  16    
                  IF/TTBF (TTBFNOT
                Node.Descendant 
                  AND/TTBF NODE.DECOMPOSITION) TTBFOR
                Node.Bound   17    
                  THEN
                Out(Node)  18    Node Pont  19  
                  RETURN