# Cross-Layer Optimization for Heterogeneous MU-MIMO/OFDMA Networks
## 4 Optimization Framework
### Reducing the Model Size  
Although the proposed model is a MILP problem, which is known to be NP-hard [28; 29], several methods for obtaining optimal solutions and their implementations have already been developed. A description of the possible methods of solving a MILP problem is beyond the scope of this paper, but we briefly explain the general concept. MILP problems are typically solved using a branch-and-bound approach [29], in which the key idea is to repeatedly solve several LP (Linear Programming)-relaxations of the original problem until the optimal solution is found. We can generate LP relaxation problems by removing all the integer restrictions on the original problem. For example, let us call the original problem P0. A new problem obtained by removing all integer constraints from P0 now becomes an LP problem, and we can easily solve it with conventional convex optimization techniques. If the solution satisfies all the constraints of P0, then it is an optimal solution, so we can stop; otherwise, we create another LP problem and try to solve it again. More specifically, in this step, we pick a variable that is restricted to an integer, but whose value in the LPrelaxation is fractional, and then generate two subproblems, P1 and P2, by imposing two different constraints on that variable. After computing optimal solutions for both P1 and P2, we can take the better of these two solutions. This process is repeated until we obtain the optimal solution. Several techniques have been proposed to accelerate the performance of the branch-and-bound approach, such as presolving, cutting planes and heuristics [29]. Most of these techniques aim to limit the size of the search space that needs to be explored by intelligently removing duplicated constraints and unnecessary branches. It is also extremely valuable to do a little extra work on the problem to reduce the number of constraints. In our case, we can do this by pre-computing the candidate routing paths for the given flows. We introduce a parameter \(Q_{lf}\), which indicates whether link \(l\) may belong to the possible routing paths of flow \(f\). By using \(Q_{lf}\), we not only narrow the lower and upper bounds on the decision variables, but also exclude unnecessary nodes and links from the optimization, so that we can further reduce the overall problem size. For example, the upper bound on the four-dimensional binary variables \(z_{lffs}\) and \(z_{lffk}\) can be more tightly determined using \(Q_{lf}\), rather than simply set to one. We can also apply this approach to the constraints in the same way: for example, in constraint (4), if we multiply \(Q_{lf}\) by the right side of the constraint, then some of the \(r_{lf}\) values quickly become zero:  
\[r_{lf}\leq\frac{1}{T}\sum_{t,s}Q_{lf}\cdot c_{lffs},\hskip 28.452756 pt\forall l,f. \tag{41}\]  
\(Q_{lf}\) can be computed with a simple DFS (Depth-First Search)-based algorithm, as shown in Algorithm 1. Please note that in line 16, we limit the maximum number of hops in the routing paths, so that unsuitable routing path candidates can be excluded from the optimization. Figure 2 shows the average computation time needed to obtain the optimal solution when \(Q_{lf}\) is applied, for a network size represented in terms of several constraints. We performed experiments by varying the model parameters, such as \(N\), \(T\), and \(F\), and taking 100 measurements of the computation time for each parameter set. Please note that even with the same parameters, the network is generated randomly each time, meaning that the number of constraints also changes. We divided a range of the number of constraints into several equal intervals, as shown in Figure 2, and calculated the average value for each interval. The measurements were conducted in the experimental environment described in Section 5.1. From the results, we can see that it takes less than 5 s until the number of constraints is lower than 5000, which is the value that can be obtained when \(N\) is around 15.