## 3 Proposed Model  
### Considerations for the Elaboration of the Parallel Algorithm  
Our model starts from a sequential algorithm that has been previously described in Reference [21], to which some improvements and modifications were made to elaborate on the parallel algorithm. The search space for the discrete knapsack problem 0-1 is given by the power set of the elements of the initial problem. If these elements are in the set \(I=\{1,2,\ldots,m\}\), then the number of subsets of the power set or parts is \(|P(I)|=2^{m}\). The power set can be represented using the terms of the empty set \(\Phi\) and the set \(I\), whereby the power set can be denoted by \(P\left(m\right)=\left[\Phi,I\right]\). If the fixed elements are in the set \(\omega_{1}\), and the elements assigned to the node are in the set \(\omega_{2}\), then \(P(m)\) can also be denoted by \(P(m)=\left[\omega_{1},\omega_{2}\right]\)[22; 23]. An example of the initial search space of a KP 0-1 with five elements is shown in Figure 1. The search space is for set \(I=\{1,2,3,4,5\}\). This space is divided into two when an item is fixed or removed. In Figure 1, the line \(l_{0}l_{0}^{\prime}\) divides the search space in two by setting and removing element 1: the left side is the left child and the right side is the right child. As can be seen in Figure 1, the search space of the left child consists of all the subsets containing element 1. On the other hand, in the search space of the right child, no subset has element 1 as its element. These two spaces correspond to level 1 of the binary tree, as shown in Figure 2.  
In turn, these search spaces are divided in two by setting and removing element 2. The line \(l_{1}l_{1}^{\prime}\) shows the spaces generated with the left child, and line \(l_{2}l_{2}^{\prime}\) shows the spaces generated with the right child. Therefore, at level 2, there will be four nodes. Each of these children is divided into two sets whose search space is a smaller dimension than the search space of the node from which they come. Figure 1: Search space \(P(m)\) of the set \(I=\{1,2,3,4,5\}\)[24]. Figure 2: Binary tree of search spaces [24]. There are two sets of level 3 for each of the sets of level 2. In level 3, there will be eight sets. In general, at the level of \(k,\ 0\leq k\leq m,\ 2^{k}\), subsets can be formed, where the search spaces of every two sets are disjointed sets and the union of all spaces of the same level is the initial power set \(P(m)\). Following this procedure, at the last level, a subset of the initial power set is assigned to each leaf [25]. In the last levels of the binary tree, most of the elements will be fixed at \(\omega_{1}\), leaving a small number of free elements. Taking into account the above, the KP 0-1 is formulated below:  
\[f_{opt}=max\left[ \begin{array}{ccc}\sum_{i\in\omega_{1}}p_{i}&+&\sum_{i\in( \omega_{2}/\omega_{1})}p_{i}x_{i}\\ \sum_{i\in\omega_{1}}w_{i}&+&\sum_{i\in(\omega_{2}/\omega_{1})}w_{i}x_{i}\leq c \\ x_{i}\in\{0,1\}&for&i\in I\end{array} \right], \tag{7}\]  
\[c=\lambda C\]  
\[C=\sum_{i=1}^{n}w_{i}, \tag{8}\]  
\[0\leq\lambda\leq 1,\ w_{i}\,,p_{i}\in Z^{+}\]  
where \(p_{i}\) is the benefit of element \(i\), \(w_{i}\) is the element weight \(i\), and \(c\) is the knapsack capacity. Equation (7) is divided into two terms: fixed \((\omega_{1})\) and free elements \((\omega_{2}/\omega_{1})\). Therefore, the formulation of the problem is adapted to the part of the problem that contains free elements: this is because it is not known which of them will be part of the solution. The modification consists of calculating the capacity of the available knapsack, once the fixed elements have been stored in the knapsack, according to Equation (9):  
\[c_{0}=c-\sum_{i\in\omega_{1}}w_{i}. \tag{9}\]  
This algorithm begins with the calculation of a feasible solution and its upper and lower limits: these are obtained as proposed by [PERSON] (1957) [18] with Equation (10).