## 2 Related Work
### 0/1-mKP Solving by Mathematical HyMKP Algorithm  
For solving the 0/1-mKP (\(m\) knapsacks, \(n\) objects), the mathematical HyMKP model (Algorithm 5) [34] (p. 893) was proposed. That hybrid model includes the MULKNAP (well-known partial BnB) program and the create-reflect-multigraph-MKP (Algorithm 6) [34] (p. 891) and two decomposition methods. Algorithm 6 was modified from the arc-flow model and the reflect model in O(\(mmC\)), \(C=\max(C_{i})\), \(i=1\), \(2\), \(\ldots\), \(m\), by starting with decreasing weights (of \(n\) items/objects) for the good initial-solution (in \(m\) knapsacks). Then, that solution was improved by the knapsack-based decomposition with \(\
u\) iterations (in \(\tau\) secs.). In the past, such mathematical models were used to solve the classical stock problem (CSP: 1999-2017) and the cutting and packing problems (1970-1977). In experiments (on OR-benchmark datasets), the mathematical HyMKP algorithm (with time complexity O(\(mmC\))) yielded 99.9% optimal solutions (in \(\tau\) secs.) for small \(n\leq 500\). ```
Step 1: perform the existing preprocessing: Instance reduction, Capacity lifting, and Item dominance. Step 2: call MULKNAP branch-and-bound (BnB) for \(\tau\) secs. if (the solution is optimal) then return. Step 3: call Create-reflect-multigraph-MKP (Algorithm 6). Step 4: for (\(i=1\) to \(\
u\)) do execute the knapsack-based decomposition. if (an optimal solution has been obtained) then return. else add the resulting no-good-cut. end for \(i\) Step 5: if (the instance is not solved) then execute the reflect-based decomposition and return. ```  
**Algorithm 5**Mathematical HyMKP model. Figure 4: Framework of QDGWO (Quantum-inspired Differential (QD) evolution with adaptive Grey Wolf Optimizer (GWO)). ```
1. \(N=\emptyset\); \(A_{s}=\emptyset\); \(A_{r}=\emptyset\); \(A_{c}=\emptyset\); \(A_{l}=\emptyset\); \(A=\emptyset\); \(s=0\); \(C=\max(C_{l})_{i=1,2,\cdots,m}\) for (\(l=1\) to \(C/2\)) do \(T[l]=0\); \(T[s]=1\); \(N=N\cup\{s\}\); \(T[s]=1\); \(N=N\cup\{s\}\);  for (\(j=1\) to \(n\)) do  for (\(l=C/2\)\(-\) 1 down to \(0\)) do  if (\(T[l]=1\)) then  if (\(l+w_{j}\leq C/2\)) then \(A_{s}=A_{s}\cup\{|J+w_{j}j,0\}|\); \(T[l+w_{j}]=1\); \(N=N\cup\{(l+w_{j})\}\);  for (\(i=1\) to \(m\)) do  if (\(l+w_{j}>C/2\) and \(l\leq C_{i}\)-(\(l+w_{j}\))) then \(A_{r}=A_{r}\cup\{|J,C_{i}\)-(\(l+w_{j}\))\(j,\mu\}\); \(N=N\cup\{(C_{i}\)-(\(l+w_{j}\))\}\);  end for \(i\);  end if;  end for \(l\);  end for \(j\);  for (\(i=1\) to \(m\)) do \(N=N\cup\{C_{i}/2\}\);  for (\(i=1\) to \(m\)) do \(A_{c}=A_{c}\cup\{|(C_{i}/2,C_{i}/2,0,i\}\);  for (\(l\)\(\in\)\(N\)) do \(A_{l}=A_{l}\cup\{|J,0,0\}\); \(l^{\prime}=\min(e\)\(\in\)\(N\): \(e>l\)); \(A=A_{s}\cup A_{r}\cup A_{c}\cup A_{l}\);  return \(N\), \(A\);
```  
**Algorithm 6**Create-reflect-multigraph-MKP in O(\(mnC\)). In particular, the arc-flow model was modified to fill a knapsack as a path in a graph, where arcs were items/objects. The looping conditions of Algorithm 6 (Lines 4-15) are similar to the basic DP (Algorithm 1) for each of \(m\) knapsacks with time complexity in O(\(mnC\)). Let (\(d\), \(e\), \(j\), \(i\)) denote an arc in a set \(A\) from nodes \(d\) to \(e\) (Lines 8, 11 and 17-19). \(A_{s}=\{(d,\,d+w_{j},\,j,\,0),\,1\leq j\leq n\}\) is the set of standard item arcs. \(A_{r}=\{(d,\,C_{i}\)-(\(d+w_{j}\)),\(j,\,i),\,1\leq i\leq m,\,1\leq j\leq n\}\) is the set of reflected item arcs (satisfying \(d+w_{j}>C_{i}/2\) and \(d\leq C_{i}\)-\(w_{j}\)). \(A_{c}=\{(C_{i}/2,\,C_{i}/2,\,0,\,i)\}\) is the set of reflected connection arcs. \(A_{l}=\{(d,\,e,\,0,\,0),\,d<e\}\) is the set of loss arcs. For solving the 0/1-mKP (in theory), the existing researches were focused on the exact algorithms, such as the branch-and-bound algorithm [35] and the mathematical HyMKP [34], where their performance results were compared to the (known) optimal solutions but those algorithms could execute in reasonable time on small \(n\leq 500\) only.