# Quantum Computing Approaches for Mission Covering Optimization
## 3 MCO Scenarios
### Scenario 2: The Buddy System  
This scenario was designed to see how different algorithms deal with additional constraints. There are two groups of resources of different types. If a resource from one group is assigned to a mission, it is required that a resource from the other group joins the same mission. Consider the previous example where a set of planes and pilots must be allocated to a set of aerial missions. A pilot and plane are required to complete a mission. Every time a plane is chosen, a pilot needs to be chosen. From an application standpoint, this scenario highlights the modeling of resource dependencies (planes depend on pilots for allocation). This scenario contains an additional row constraint. The list of constraints is as follows:  
* Column constraint: a resource can be assigned at most to one mission. This is the hard constraint of the problem. * Row constraint: if a type of resource is chosen, then a resource of the second type must also be chosen. We call it the _buddy_ constraint. This is the additional constraint added in this scenario. The entire set of rules for this scenario is as follows: 1. The set of missions in the problem is \(\mathbf{M}=\{m_{1},\ldots,m_{N_{m}-1},U\}\). 2. The set of resources is \(\mathbf{R}=\{r_{1},\ldots,r_{N_{r}}\}\). 3. There are two qualifications \(\mathbf{Q}=\{q_{1},q_{2}\}\), which means that resources are divided in two groups: \(\mathbf{R}_{1}\) and \(\mathbf{R}_{2}\). 4. Resource's capability is \(\mathcal{C}\colon\mathbf{R}\times\mathbf{Q}\rightarrow\{0,1\}\), which means that all resources that are qualified have the same capability. Resources have only one qualification:
* The set of all resources that have capability \(1\) for qualification \(q_{1}\) is notated as \(\mathbf{R}_{1}\). * The set of all resources that have capability \(1\) for qualification \(q_{2}\) is notated as \(\mathbf{R}_{2}\). * The sets \(\mathbf{R}_{1}\) and \(\mathbf{R}_{2}\) do not contain the same resource: \(\mathbf{R}_{1}\cap\mathbf{R}_{2}=\{\}\). * The sets \(\mathbf{R}_{1}\) and \(\mathbf{R}_{2}\) contain all resources: \(\mathbf{R}_{1}\cup\mathbf{R}_{2}=\mathbf{R}\). * The number of resources in \(\mathbf{R}_{1}\) and \(\mathbf{R}_{2}\) is the same \(|\mathbf{R}_{1}|=|\mathbf{R}_{2}|\). 5. Missions require resources with qualification \(q_{1}\) and not \(q_{2}\). Therefore, the mission require function can be formally described as: \(\textsc{REQ}_{M}\colon\mathbf{M}\times\{q_{1}\}\rightarrow\mathbb{Z}_{\geq 0}\). 6. The resource's requirement is called the _buddy requirement_. Every resource when allocated requires another resource with the opposite qualification. * \(\textsc{REQ}_{R}(r,1)=0\) & \(\textsc{REQ}_{R}(r,2)=1\) & \(\textsc{REQ}_{R}(r,2)=0\) & \(\textsc{REQ}_{R}(r,1)=1\) & \(\textsc{REQ}_{R}(r,2)=0\) & \(\forall r\in\mathbf{R}_{2}\) 7. As in the previous scenario, the objective function measures the total mission cost. The mission cost formulation is exactly the same as the secondary resources scenario. However, the way we view the problem in its matrix representation is slightly different, as shown in Figure 2.
The primary difference between this solution and the prior scenario's solution is that now there are _buddy_ constraints present along the rows of the matrix (for this reason, it is also called the _row_ constraint). For example, in Figure 2, the first row related to the first mission has two resources allocated from \(\mathbf{R}_{1}\). In order for the buddy constraint to not be violated, two resources from \(\mathbf{R}_{2}\) are allocated to that mission. The solution shown is valid since no rows or columns violate any of the constraints. The solution also has the lowest mission cost since the mission requirements were all exactly met. Finding optimal solutions for this scenario is trivial since all resources within the same group are indistinguishable from each other in terms of allocation cost. However, when adding different capabilities to resources within this MCO, the complexity of finding the optimal solution increases.