## 4 Solution Algorithms
### Stage-Wide Problem Decomposition Schemes of GLB  
A good lower bound for a combinatorial optimization problem should be tight and easy to compute compared with solving the problem itself [53]. The GLB can easily provide relatively tight lower bounds. The request for decomposition for QAP or other problems such as coupling decisions has the following stated objectives: (1) decouple the decisions and the original problem can be divided into simple subproblems; (2) provide the basis for aggregation techniques and form the backbone of the procedures; (3) the problem can be solved finally by coordinating the solution of linear subprograms. These objectives need to be achieved in absolute terms of course, but also in a pragmatic way if the results of decomposition are expected to have a significant impact on real-world planning and decision-making. This means that the tools and methodology developed must be sufficiently accurate, reliable, and consistent to meet decision making needs. In this section, we first briefly introduce the solution principle of GLB, of which details can be found in [54]. Figure 9 considers an illustrative example with \(|N|=4\) (where \(N\) is defined as set of facilities, index \(i,j\in N\), and \(M\) are defined as the set of locations, and index \(k,l\in M\), \(|M|=|N|\)), which is adapted from the classical QAP instance of the NEOS ([[https://neos-guide.org/case-studies/sc/la/qap/qap-of-size-4/](https://neos-guide.org/case-studies/sc/la/qap/qap-of-size-4/)]([https://neos-guide.org/case-studies/sc/la/qap/qap-of-size-4/](https://neos-guide.org/case-studies/sc/la/qap/qap-of-size-4/)), accessed on 7 May 2023). For this example, there are four facilities (Figure 8(a)) that need to be allocated to four locations (Figure 8(b)) following the one-to-one assignment constraints. Figure 8(c) provides a feasible solution, i.e., permutation (A-2, B-1, C-3, D-4). In Figure 10, we would like to highlight the symmetrical two-stage decision feature of this instance, where the first stage aims to determine the locations of the flow-sending facilities and where the second stage is concerned about the locations of flow-receiving facilities. Figure 10: The two-stage decision form of the instance. Figure 9: An instance of standard QAP. From a dynamic programming-oriented perspective, we describe the process of obtaining GLB as three steps: (1) the decisions at the second stage are decomposed into a collection of simpler linear assignment problems (LAPs); (2) sequential solving of each LAP; (3) their solutions are used as the backward cost estimate (BCE) when making first-stage decisions. This three-step process is further illustrated in Table 6.  
As presented in Tables 7 and 8, for the given input data (distance matrix and flows), we detail the calculation steps as shown below. \begin{table} \begin{tabular}{c c c} \hline \hline
**Step** & **Formula** & **Illustration** \\ \hline \hline \end{tabular}  \begin  
Step 1: Calculate the \(\pi_{ik}^{*}\) for each \((i,k)\) pair. For example, let \(x_{A1}=1\) then we need to assign three flows \((f_{AB},f_{AC},f_{AD})\) to three distances \((d_{12},d_{13},d_{14})\), as shown in Figure 11. The objective is to find the minimum value of the sum of products of flows and distances. The LAP can be simply solved using sorting algorithms [55] to match the minimum flows with the maximum distances. Accordingly, the optimal solution of the LAP for \(x_{A1}=1\) is \(\pi_{kl}^{*}=f_{AB}d_{12}+f_{AC}d_{14}+f_{AD}d_{13}=22\times 3+53\times 2+53 \times 0=172\). Step 2: For each \((i,k)\) pair, we calculate the total cost \(c_{ik}\) for each \((i,k)\). By using Table 9 with BCE \(\pi_{ik}^{*}\), we calculate \(c_{ik}=b_{ik}+\pi_{ik}^{*}\), where \(b_{ik}=0\) in this instance and \(c_{ik}=\pi_{ik}^{*}\).