# Quantum Computing Approaches for Mission Covering Optimization
## 4 Algorithm Implementation
### Scenario 1 (One Constraint)  
#### 4.1.1 QA and QAOA  
The goal of the MCO problem is to minimize the total cost. Various methods are used to define the mission cost. The following formulation takes into account the limitations of QUBO. In the rest of the paper, \(QA\) denotes QUBO problems performed on quantum annealing machines, while QAOA and QAOAH denote QUBO problems executed on gate-based architectures. The optimal mission cost occurs when all the resources required are allocated. Or, formally, consider mission \(m\); the optimal mission cost occurs when:  
\[\sum_{r\in\mathbf{R}}x_{m,r}=\text{REQ}_{M}(m,1). \tag{1}\]  
The \(x\) values represent Booleans (an alternative representation of the solution \(f_{s}\)), such that when indexed by \(m\in\mathbf{M}\) and \(r\in\mathbf{R}\), e.g., \(x_{m,r}\), it represents whether or not the solution mapped resource \(r\) to mission \(m\). As an example, suppose there are three resources, \(\mathbf{R}=\{1,2,3\}\) and the first mission requires two of them, then the optimal mission cost for the mission occurs when:  
\[x_{1,1}+x_{1,2}+x_{1,3}=2. \tag{2}\]  
Equation (2) is true when two out of the three variables are true. The mission cost represents the penalty added any time a mission lacks one or more needed resources. The penalty is higher when more resources are missing. A squared error is used to represent the mission cost:  
\[\mathsf{MC}(x,m)=\Bigl{(}\sum_{r\in\mathbf{R}}x_{m,r}-\text{REQ}_{M}(m,1) \Bigr{)}^{2}, \tag{3}\]  
where \(\mathsf{MC}(x,m)\) is the cost associated with mission \(m\). It can be seen from Equation (3) that the minimum mission cost, when \(\mathsf{MC}(x,m)=0\), yields the optimal case, as described in Equation (1). The mission cost is quadratic. The example that yielded the optimal case in Equation (2) in terms of the mission cost function is:  
\[\mathsf{MC}(x,1)=(x_{1,1}+x_{1,2}+x_{1,3}-2)^{2}. \tag{4}\]  
For this optimization problem, secondary resources should be allocated only after primary resources are allocated first. Therefore, we introduce precedence costs for resources. Equation (5) shows the ideal condition regarding the allocation of secondary resources. \[\sum_{m\in\mathbf{M}}x_{m,r}=\mathsf{C}(r,1)-1\quad\forall r\in\mathbf{R} \tag{5}\]  
The precedence cost is dependent on the capability of a resource and, therefore, dependent on whether or not this resource is primary or secondary. When the resource is primary, the ideal condition means that the it must be allocated to one of the active missions (apart from the unallocated/psuedo mission). For the other secondary resources, ideally none are used. The precedence cost may or may not be met when optimizing, so similarly to mission cost, precedence cost is the squared error of this equality:  
\[\mathsf{PC}(x,r)=\biggl{(}\sum_{ \begin{subarray}{c}m\in\mathbf{M}\\ m\
eq U\end{subarray} }x_{m,r}-\mathsf{C}(r,1)+1\biggr{)}^{2}. \tag{6}\]  
Finally, the objective function is then the total mission cost and the total precedence cost in the MCO:  
\[f_{obj}(x)=\sum_{m\in\mathbf{M}}\mathsf{MC}(x,m)+\frac{1}{|\mathbf{R}|}\sum_{ r\in\mathbf{R}}\mathsf{PC}(x,r). \tag{7}\]We weight the precedence cost by \(\frac{1}{|\mathbf{R}|}\) to ensure that the mission cost is minimized before precedence cost. The total cost is the sum of the mission cost and the precedence cost, and it is reflected in the objective function. The constraint that a resource must be paired to exactly one mission is formulated:  
\[\sum_{m\in\mathbf{M}}x_{m,r}=1\quad\forall r\in\mathbf{R}. \tag{8}\]  
The constraint function used for this scenario is defined as  
\[\mathsf{CONSTR}(x,r)=\Big{(}\sum_{m\in\mathbf{M}}x_{m,r}-1\Big{)}^{2}. \tag{9}\]  
Since the QUBO is used to solve problems without constraints, we must add it to the objective function so that when it minimizes, the constraints will be met. The method of Lagrange multipliers is a strategy for finding the local maxima and minima of functions subject to equality constraints.