can you solve this $($a$)$ Give a short description of tabu search. In your description the notions of

a legal neighbour, a tabu list and an aspiration level should be mentioned.

$($b$)$ Consider the graph $H$ in Figure $1.$ The $2-$PATH PROBLEM is the problem of

finding a minimum weight path with two edges. Let dab be an initial solution

for the $2-$PATH PROBLEM on $H.$ Using the swap neighbourhood perform four

iterations of the basic tabu search algorithm to improve the initial solution.

The tabu times for deleted and added edges are $2$ and $1,$ respectivelv. For

each iteration, give the corresponding path and all tabu times.

$($c$)$ Let $G$ be a bipartite graph with vertices

$V(G)=\{1,2,3,4,5,1^{\text{'}},2^{\text{'}},3^{\text{'}},4^{\text{'}},5^{\text{'}}\}$

and edges

$E(G)=\{{11}^{\text{'}},{13}^{\text{'}},{15}^{\text{'}},{21}^{\text{'}},{22}^{\text{'}},{32}^{\text{'}},{43}^{\text{'}},{51}^{\text{'}},{54}^{\text{'}}\}.$

Starting from the matching $M=\{{11}^{\text{'}},{22}^{\text{'}},{43}^{\text{'}},{54}^{\text{'}}\}$ of $G,$ find a maximum

matching of $G.$

$($d$)$ Describe the patching algorithm for the Asymmetric TSP$.$ Describe, in par$-$

ticular, how to compute the cheapest collection of disjoint cycles covering all

the vertices and how to find the cheapest patching of two cycles. What is

the running time of the patching algorithm?