# An Approach to Aid Decision-Making by Solving Complex Optimization Problems Using SQL Queries
## 2 Materials and Methods
### Maximum Clique Problem  
A clique in a graph is defined as a subgraph with pairwise adjacent vertices. The number of vertices contained in a clique determines its size. Finding the largest clique in a graph is an NP-complete problem, and it is referred to as the Maximum Clique Problem (MCP). Applications of this problem appear in different domains such as stock markets [18], collaboration in industry networks [19], social network analysis [20], detection and resolution of conflicts between aircraft [21], and matching protein structures [22], among others. The MCP can be defined as follows: given a graph \(G=(V,E)\), where \(V\) is the set of vertices and \(E\) is the set of edges, is there a subgraph \(S\subseteq G\) such that \(S\) is a maximum clique \(\mathcal{K}_{p}^{*}\)? \[\mathcal{K}_{p}^{*}=\{S:S=\max\{|G^{\prime}|:G^{\prime}\subseteq G,G^{\prime} \text{ is a clique}\}\} \tag{3}\]  
A clique \(\mathcal{K}_{p}\) is a subgraph \(S=\{V^{\prime},E^{\prime}\}\) that is complete and has \(p=|V^{\prime}|\) nodes. A subgraph \(S\) is complete if every pair of nodes \(i,j\in V^{\prime}\) has \((i,j)\in E^{\prime}\), where \(i\
eq j\). The mathematical formulation for the MCP is shown in Equation (4), which is based on a graph \(G=(V,E)\), where \(\overline{E}\) is the complement of the set of edges [23]. The complement refers to those edges that do not belong to \(E\). The formulation maximizes the number of nodes that have in common all their possible edges. \[ \begin{split}\max\sum_{i=1}^{n}x_{i},& s.t.& x_{i}+x_{j}\leq 1,\forall(i,j)\in\overline{E},\\ & x_{i}\in\{0,1\},i=1,\ldots,n\end{split}  \tag{4}\]  
\[ \begin{split}\text{where},\quad x_{i}=\left\{\begin{array}{ll}1& \text{if node $i$ belongs to the}\\ &\text{maximum clique}\\ 0&\text{otherwise}\end{array}\right.\end{split} \] \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(\mathcal{I}\) & \(\boldsymbol{s_{1}}\) & \(\boldsymbol{s_{2}}\) & \(\boldsymbol{s_{3}}\) & \(\boldsymbol{s_{4}}\) & \(\boldsymbol{s_{5}}\) \\ \hline
0 & 0 & 0 & 0 & 0 & 0 \\
20 & 6 & 5 & 3 & 4 & 4 \\
40 & 9 & 8 & 5 & 6 & 5 \\
60 & 13 & 11 & 8 & 8 & 9 \\
80 & 16 & 13 & 10 & 10 & 10 \\
100 & 18 & 15 & 12 & 11 & 11 \\
120 & 20 & 16 & 15 & 13 & 12 \\
140 & 22 & 17 & 16 & 14 & 17 \\
160 & 23 & 18 & 17 & 15 & 18 \\
180 & 26 & 19 & 19 & 16 & 19 \\
200 & 28 & 20 & 20 & 17 & 22 \\ \hline \hline \end{tabular}
\begin{tabular}{c c} \hline \hline
**SELECT** & \(<\)security investments\(>\), \(<\)profit definition\(>\) \\
**FROM** & \(<\)vector \(e\) definition\(>\) \\
**WHERE** & \(<\)constraint definition\(>\) \\
**ORDER BY** & profit **DESC LIMIT 1** \\ \hline  & \(<\)security investments\(>\) := \\  & \(\beta_{1}.\mathcal{I},\ldots,\beta_{K-1}.\mathcal{I}\) \\  & \(<\)profit definition\(>\) := \\  & \((\beta_{1}.s_{1}+\beta_{2}.s_{2}+\ldots+\beta_{K-1}.s_{K-1})\) as profit \\  & \(<\)vector \(e\) definition\(>\) := \\  & \(\beta\) as \(\beta_{1}\), \(\beta\) as \(\beta_{2}.\cdots\), \(\beta\) as \(\beta_{K-1}\) \\  & \(<\)constraint definition\(>\) := \\  & \((\beta_{1}.\mathcal{I}+\beta_{2}.\mathcal{I}+\ldots+\beta_{K-1}.\mathcal{I}\leq \mathcal{Q})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Database table comprising the information of a PSP instance \((S,\mathcal{I},\beta,\mathcal{Q})\). Figure 1: BNF format of the general SQL query that solves the PSP. Given an instance of the MCP, as a graph \(G=(V,E)\), and an integer \(K\), \(1\leq K\leq N\), [PERSON] et al. [16] introduced an exact approach, based on SQL queries, to find the maximum clique in a given \(G\) graph. Figure 2 shows the general SQL query in BNF notation [24] that solves MCP instances. The query uses tables for the set of edges and the set of nodes. The table for the nodes comprises the nodes of the graph \(V\) that will be changed. The table for the edges contains two columns (\(n_{1}\) and \(n_{2}\)) to represent an edge per row and an additional column \(s\) to identify the clique. The value one is associated with each edge in the original set \(E\).