# A Model-Driven Approach for Solving the Software Component Allocation Problem
## 4 Component Allocation Problem  
The component allocation problem (CAP) addresses the assignment of components to units. Each component must be assigned to exactly one unit. Such an allocation of a component consumes resources of the corresponding unit. Each unit, in turn, has a maximum capacity for each resource which shall not be violated for any feasible component allocation. The goal is to find an optimal component allocation that minimizes the consumption of each resource and does not violate any maximum resource capacity. Let us assume a system consisting of \(U\) units and \(C\) components to be allocated. Each unit offers \(M\) resources that are consumed by an allocation. The \(m\)-th resource consumption (\(1\leq m\leq M\)) of an assignment of the \(i\)-th component (\(1\leq i\leq C\)), to the \(j\)-th unit (\(1\leq j\leq U\)) is given by \(T_{jm}\) and the maximum capacity by \(R_{jm}\). A component allocation is given by the binary matrix \(\mathbf{x}\) of shape \(C\cdot U\) where \(x_{ij}=1\) expresses an assignment of the \(i\)-th component to the \(j\)-th unit. Since a component must be assigned to exactly one unit, \(\sum_{j=1}^{U}x_{ij}=1\) for each component \(i\) must hold. Since the overall resource consumptions are conflicting with each other, all possible Pareto-optimal solutions shall be found. We refer to this constrained multi-objective optimization problem as multi-objective component allocation problem (MOCAP), which is stated as follows:  
\[\text{Minimize}\quad f_{m}(\mathbf{x})=\sum_{i=1}^{C}\sum_{j=1}^{U}x_{ ij}\cdot T_{ijm} \forall j\in(1,\dots,M)\] (1) subject to \[\sum_{i=1}^{C}x_{ij}\cdot T_{ijm}\leq R_{jm} \forall m\in(1,\dots,M),\ j\in(1,\dots,U) \tag{1a}\] \[\sum_{j=1}^{U}x_{ij}=1 \forall i\in(1,\dots,C)\] (1b) \[x_{ij}\in\{0,1\}, \forall i\in(1,\dots,C),\ j\in(1,\dots,U). \tag{1c}\]  
The goal of MOCAP is to find the Pareto-optimal set of component allocations. A solution is called Pareto-optimal if there is no other solution that dominates it. An allocation \(\mathbf{x}\) dominates another allocation \(\mathbf{y}\), if \(f_{m}(\mathbf{x})\leq f_{m}(\mathbf{y})\) for all \(1\leq j\leq M\), and there exists at least one resource \(m\) where \(f_{m}(\mathbf{x})<f_{m}(\mathbf{y})\). Their corresponding resource consumption values are mapped to the objective space and referred to as Pareto-front. Instead of solving the multi-objective problem directly, the objectives can be aggregated to a single cost function to minimize. The objective function is defined as follows:  
\[f^{(w)}(\mathbf{x})=\sum_{m=1}^{M}w_{m}\cdot\left(\sum_{i=1}^{C}\sum_{j=1}^{U} x_{ij}\cdot T_{ijm}\right) \tag{2}\]  
where \(w_{m}\) is the trade-off weight assigned to the \(m\)-th resource. Note that the trade-off weights \(w\) need to satisfy the following condition:  
\[\sum_{m=1}^{M}w_{m}=1 \tag{3}\]  
for an allocation to be feasible. Figure 1 demonstrates an example of a component allocation problem. There are three components (\(C=3\)), two units (\(U=2\)), and two resources (\(M=2\)). The problem can be converted to a bipartite graph with different vectors or resources as weights on each edge. The resource capacity and consumptions are annotated by a vector notation for brevity. For instance, \(T_{11}=(T_{111},T_{112})=(7,15)\). A concrete allocation is represented by red solid lines. The allocation sets \(x_{12}\), \(x_{22}\), \(x_{31}\) to one, and all other entries in \(\mathbf{x}\) to zero. The resource capacity of Unit \(1\) is not violated since \(4<R_{11}=13\) and \(8<R_{12}=25\) as well as the capacities of Unit \(2\)\(14<R_{21}=20\) and \(22<R_{22}=30\). Thus, this is a feasible component allocation with \(f(\mathbf{x})=(4+14,8+22)=(18,30)\). For the single-objective scalarization with \(w=(0.75,0.25)\) this results in \(f^{(w)}(\mathbf{x})=21\). Table 1 shows the set of all possible allocations in the component allocation problem example. For each allocation, the table shows whether it is feasible. In addition, it shows the values for \(f^{(w)}(\mathbf{x})\) and \(f(\mathbf{x})\).