## 3 Proposed Model
### Multi-BB Algorithm for a Multicore Cluster  
In the implementation of the multi-BB algorithm in the multicore cluster (Figure 4), four factors that influence its efficiency are considered: shared knowledge, knowledge utilization, work division, and synchronization [13]. These are defined to have a good load balance, a minimum number of synchronization points, and the shortest communications times.  
Figure 4: Flowchart of the parallel multi-BB algorithm.  
Shared knowledge, or the subsets that are generated by the branching of trees, is stored in local lists in each processing unit because each of the multi-BB trees is independent of the others. An Exclusive Read, Exclusive Write, Parallel Random Access Machine (EREW PRAM) model is used for access to the subsets and to write the partial solution. Figure 4 shows how the local lists are used in each processing unit, from how they are started and updated to when the subsets are taken.  
For division of the work, both in a static form and at the beginning of the calculation, a tree is assigned to each processing unit. Each decision tree is expected to grow, and a good load balance is achieved. This is the first activity that the processes perform, as is seen in Figure 4.  
With regard to the use of knowledge and synchronization, the optimal solution is shared knowledge. The processing units are synchronized to exchange partial solutions and determine the optimal solution to the problem. A processing unit receives partial solutions, obtains the optimal solution, and stores the identification of the processing unit within that solution. The above process is presented in a green box in Figure 4. The number of local iterations to carry out the synchronization is based on the proposal by [PERSON] [24].  
The algorithm is asynchronous when each processing unit travels through its search space. Synchronization occurs when the processes send and receive information (blue lines in Figure 4). Communications C1, C4, and C5 are executed only once during the entire calculation process. In communication C1, the elements in \(\omega_{1}\) and \(\omega_{2}\) of the problem are sent. In communication C4, the master processor sends data to all others and the number of the processing unit that calculated the optimal solution. In communication C5, the processing unit with the optimal solution sends the data to the master processor of the optimal solution, such as \(\omega_{1}\), \(\omega_{2}\) (the set of solution elements for \(f_{linear}\) and \(f_{opt}\)). Communications C2 and C3 are made each time the maximum number of local iterations is reached. In both cases, only two datapoints are sent. In communication C2, the master sends the updated global solution and the signal to the processing units to continue the calculations. In communication C3, each processing unit sends its \(f_{opt}\) solution and the status of its local list.  
The multi-BB algorithm was programmed in ANSI C, and the Message Passing Interface (MPI) library is used to pass messages. The number of maximum local iterations is one-tenth the size of the problem [24]. The proposed distribution for the parallel processes number is described in Section 4.2. The remaining variables have been previously described.