## 2 The Multi-Demand Multidimensional Knapsack Problem  
In this section, the formulation of the MDMKP is provided, followed by a focused review of prior studies relevant to the techniques employed in this work. The MDMKP is an expanded version of the Multidimensional Knapsack Problem (MKP). It is formulated as follows: Let \(V=\{1,\ldots,n\}\) represent the collection of items, and \(C=\{c_{1},\ldots,c_{m},\ldots c_{m+q}\}\) constitute the set of constraints. A profit \(p_{j}\) is associated with each item. The objective is to maximize \(z\), as shown in Equation (1), where \(x_{j}\) is 1 if item \(j\) is selected and 0 otherwise. Constraints are defined by \(m\) inequalities in Equation (2) and \(q\) inequalities in Equation (3):  
\[\text{Maximize}\quad z=\sum_{j=1}^{n}p_{j}x_{j} \tag{1}\] \[\text{subject to}\quad\sum_{j=1}^{n}a_{ij}x_{j}\leq c_{i},\quad \forall i\in\{1,\ldots,m\}\] (2) \[\quad\sum_{j=1}^{n}a_{ij}x_{j}\geq c_{i},\quad\forall i\in\{m+1, \ldots,m+q\} \tag{3}\]  
Distinct from the MKP, the MDMKP permits values of \(p_{i}\) to be less than, equal to, or greater than zero, and also incorporates the greater-than-or-equal constraints found in Inequality (3). The inequalities present in Equation (2) are identified as knapsack constraints, whereas those present in Equation (3) are acknowledged as demand constraints. The MDMKP has been observed to garner less attention than the MKP, potentially due to its two types of constraints which complicate the identification of feasible solutions. Both exact and heuristic methods have been explored in the literature. For example, general mixed-integer programming solvers such as CPLEX have been effectively employed to solve instances with \(n\leq 100\) within a reasonable time span [12, 13]. However, for larger instances, the existing procedures often latter in pinpointing an optimal solution. Consequently, various heuristic approaches have been introduced to tackle large instances. In [14], a two-stage tabu search algorithm is employed where neighborhoods with diverse structures are utilized. Initially, a tabu search is conducted to explore infeasible regions. Following the establishment of feasibility, a second tabu operation is executed to solely scrutinize feasible solutions. A straightforward iterative search strategy was implemented in [15] to resolve the MDMKP. This strategy employed the adaptive memory and learning techniques derived from the tabu search. The search hinged on a strategic oscillation around feasibility boundaries, orchestrating the interaction between the alterations in objective function values and the changes in feasibility. Subsequently, standard aspiration criteria and dynamic short-term tabu tenure were applied. In [16], the authors developed a black-box scatter search approach for general categories of binary optimization problems and evaluated their method using the MDMKP, amongst other binary problems. Additionally, the solution addressed MDMKP constraints through a static penalty approach. A solution-based tabu search method was investigated in [12]. This algorithm was designed in two unique stages. The first stage involved identifying a promising hyperplane within the entire search space, and the second stage aimed to discover improved solutions by probing the subspace of the hyperplane. Moreover, the key components of the algorithm were evaluated to discern their impacts on the algorithm's performance. In [17], a hybrid algorithm was presented that combined the k-means method with binary versions of the cuckoo search and sine cosine algorithms to solve the NP-hard MDMKP. The effectiveness of the algorithm was proven through extensive experiments, which demonstrated its superior performance over other binarization methods. In particular, integrating a repair operator improved results by an average of 0.23%, while the k-means operator outperformed the random operator by an average of 1.06% for cases with 100 items and 30-30 restrictions. The MDMKP has numerous real-world applications across various domains. For example, ref.