<jupyter_start><jupyter_text>Prepared by  <NAME>          Examples for QUBO Formulation In the previous section, we learnt about the penalty method for constrained problems. Now, lets apply it to some important constrained optimization problems.   Travelling Salesman Problem (TSP) Recall, given a set of cities and corresponding distances between each pair of cities, the problem is to find the shortest possible route such that a salesman visits every city exactly once and returns to the starting point / hometown. So, eventually, the salesman maximizes his sales by minimizng the total cost of travelling between the nodes.  Hamiltonian CycleA path through a graph that visits each node (city) exactly once is called a Hamiltonian path or a **Hamiltonian cycle**. To define the mathematical formulation, the problem asks for the shortest Hamiltonian cycle that can be taken through each of the nodes. So, we will find the shortest Hamiltonian cycle in a graph $G = (V,E)$ with N nodes and costs $w_{ij}$ (cost of travelling from node $i$ to node $j$). Here $V =\{1,...N\}$ is the set of nodes and E is the edge set. The cycle is defined using $N^2$ binary variables $x_{i,p}$, where $i$ represents the node and $p$ represents the order in that cycle. The variable results in 1 if salesman passes node $i$ if its at position $p$ in the route.$$x_{ip}=\left\{\begin{array}{ll}       1, & \text{node i is at position p in the route} \\      0, & \text{otherwise} \\\end{array}\right.$$ Directed vs Undirected GraphsThe nodes are labelled 1 to N and the edge set can be:* directed: order $(i,j)$ matters* undirected: order doesn't matter We will assume our graph to be directed with edge set $(i,j)$. We can extend to undirected graphs by just considering a directed graph with $(j,i)$ added to the edge set E whenever $(i,j)$ is added to the edge set E. ConstraintsThe problem involves the following constraints:1. Each node can only appear once in the whole cycle.$$\sum_{i=1}^{N} x_{i,p} = 1 \;\;\;\;\; \forall p$$2. For each time, a node has to occur.$$\sum_{p=1}^{N} x_{i,p} = 1 \;\;\;\;\; \forall i$$3. If the graph isn't fully connected such that there exists $(i,j) \notin E$, so for a given route order, if $x_{i,p}$ and $x_{j,p+1}$ are both 1 (the nodes are in a given order but there is no edge linking them), there will be an energy penalty.$$\sum_{(i,j) \notin E} \sum_{p=1}^{N} x_{i,p} x_{j,p+1} > 0$$ Objective FunctionThe cost that needs to be minimized is:$$C(x) = \sum_{(i,j) \in E} w_{ij} \sum_{p=1}^{N} x_{i,p} x_{j,p+1}$$Now, including the constraints to get a single objective function:$$C(x) = A\sum_{(i,j) \in E} w_{ij} \sum_{p=1}^{N} x_{i,p} x_{j,p+1} + B\sum_{p=1}^{N} \left(1-\sum_{i=1}^{N}x_{i,p}\right)^2 + B\sum_{i=1}^{N} \left(1-\sum_{p=1}^{N}x_{i,p}\right)^2 + B\sum_{(i,j) \notin E} \sum_{p=1}^{N} x_{i,p} x_{j,p+1}$$Here, A should be small enough so not to violate the constraints whereas B is a positive penalty parameter that should be large enough for the constraints to be considered. One possibility can be $0<A\max (w_{ij})<B$ (assuming that $w_{ij} \geq 0$ for each $(i,j) \in E$).  Task 1Let's assume we have the following fully-connected, undirected graph of 4 nodes / cities and 6 edges, $G = (4,6)$. Determine the matrix Q for this graph. (You may assume suitable values for A and B).  [Click here for solution](QUBO_Examples_TSP_Solutions.ipynbtask1)***  Task 2Input matrix Q calculated in Task 1 to the function *qubo_solver()* and determine $x$ which minimizes $x^T Qx$ and the corresponding minimum value.<jupyter_code># Access the qubo_solver() function
%run qubo_functions.py

# Define the Q matrix



# Pass the matrix as an argument to the function
qubo_solver(Q)<jupyter_output><empty_output><jupyter_text>[Click here for solution](QUBO_Examples_TSP_Solutions.ipynbtask2)***  Task 3Using the QUBO algebraic expression and testing all possibilities of $x$, verify your result for Task 2. (You may use a Python code for this task).<jupyter_code>#Create a function to evaluate the value of objective function for each x.

def tsp_task_3(x):
    #INSERT YOUR CODE HERE!
    
    
    
    return y

#Minimize the function for all possibilites of x.
#The following code generates the possile permutations of x and calculates the value of the objectve funtion for each.
import numpy as np
import itertools
possible_values = {}
vec_permutations = itertools.product([0,1], repeat=20)    # A list of all the possible permutations for x vector
for permutation in vec_permutations:
    x = np.array([[var] for var in permutation])         # Converts the permutation into a column vector
    value = tsp_task_3(x)
    possible_values[value[0]] = x
    vector = tuple(x.T[0])
    # print("Vector x =", vector, "; Value =",int(value))  # Displays every vector with its corresponding value
    
min_value = min(possible_values.keys())                  # Lowest value of the objective function
opt_vector = tuple(possible_values[min_value].T[0])      # Optimum x corresponding to lowest value
print("---")
print("The vector x =", opt_vector, "minimizes the objective function to a value of", int(min_value))<jupyter_output><empty_output><jupyter_text>[Click here for solution](QUBO_Examples_TSP_Solutions.ipynbtask3)***  Task 4Let's assume we have the following fully-connected, undirected graph of 5 nodes / cities and 10 edges, $G = (5,10)$. Determine the matrix Q for this graph. (You may assume suitable values for A and B).  [Click here for solution](QUBO_Examples_TSP_Solutions.ipynbtask4)***  Task 5Input matrix Q calculated in Task 4 to the function *qubo_solver()* and determine $x$ which minimizes $x^T Qx$ and the corresponding minimum value.<jupyter_code># Access the qubo_solver() function
%run qubo_functions.py

# Define the Q matrix
Q2 = 


# Pass the matrix as an argument to the function
qubo_solver(Q2)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10816777041942605, 'fraction_numerical': 0.011377143827474954, 'mean_word_length': 4.49953314659197, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '236223', 'license': 'MIT', 'n_tokens_mistral': 1844, 'n_tokens_neox': 1745, 'n_words': 797, 'path': 'notebooks/.ipynb_checkpoints/QUBO_Examples_TSP-checkpoint.ipynb', 'repo_name': 'ozlemsalehi/qa-edu', 'size': '5901'}