# An Approach to Aid Decision-Making by Solving Complex Optimization Problems Using SQL Queries
## 3 Experimental Design and Results
### Second Experiment: Other Problems
#### 3.2.2 Case Study: Knapsack and Channel Assignment Problem  
This section shows how to adapt the SQL queries that solve the PSP and 3 CG to solve instances of the Knapsack and Channel Assignment problems.  
Let us begin with the Knapsack Problem: defined by a maximum weight \(W\), a set of objects \(O=\{o_{1},o_{2},\cdots,o_{n}\}\) having each object \(o_{i}\) an associated weight \(w_{i}\) and value \(v_{i}\). The problem searches to maximize the value of a chosen subset of objects \(O^{\prime}\subseteq O\) while avoiding exceeding the maximum capacity \(W\) (see [34]). This problem has a straightforward transformation into the PSP. A tuple \((S,\mathcal{I},\beta,Q)\) can be defined as follows. The set \(S\) of  
Figure 4: BNF syntax of a SQL query that determines the \(G\) graph used to identify possible self-referencing groups. (**a**) To identify all the pairs \((i,j)\). (**b**) To identify the edges of the graph.  
securities is formed by the \(n\) objects; hence, \(S=\{s_{1},s_{2},\cdots,s_{n}\}\). The investment portions \(I\) are defined according to the weights of the objects. The quantity \(\mathcal{Q}\) will be equal to the maximum weight \(W\). Finally, the expected return matrix \(\beta\) will set a cell \(\beta_{i,j}=v_{j}\) if the investment \(q_{i}\) is equal to its weight; otherwise, \(\beta_{i,j}=0\). The SQL query can be used without modification to solve the Knapsack Problem with this transformation in mind.  
The Channel Assignment Problem (CAP) (inspired by its implementation in [31]) is almost as simple as the Knapsack one, except for a minor change in the SQL query to be fully applied.  
Taking into account the definition in [14], the CAP is a natural generalization of graph coloring. The problem associates weights with the edges of a graph. For example, the special case of the CAP called One-Bounded CAP is equivalent to graph coloring. It searches to assign values to nodes between \(\{1,\cdots,K\}\) with the smallest integer \(K\) possible such that the difference \(|v(x)-v(y)|\geq 1\), where \((x,y)\) are edges of the graph \(G\) that defines the instance of the problem. When a value \(l\) is used instead of 1 in CAP, the problem is called \(l\)-bounded CAP, and this one generalizes graph coloring.  
The SQL query defined in Section 2.3 to solve the 3 CG can be slightly modified to solve the more general \(l\)-CAP problem. This only requires modifying the \(<constraint\;definition>::=V_{i}.color<>Vj.color\;AND\cdots\) in the SQL proposed, such that it transforms into something like this: \(<constraint\;definition>::=(V_{i}.color-Vj.color)>=weight(v_{i},v_{j})AND\cdots\), where \(weight(v_{i},v_{j})\) is the information concerning the weight associated with the \(edge(v_{i},v_{j})\) in the graph instance. This latter information can be introduced as a constant when expanding the SQL statement or as a table for the database.  
The use of the solutions for the PSP, MCP, and 3 CG to solve other optimization problems shows the validity of using SQL queries as an alternative to solve complex optimization problems.