Give an informal description of the Assignment Problem $($AP$).$ Provide an Integer

Programming formulation of AP$.$ Explain the meaning of all parameters, variables

and constraints.

Describe the greedy algorithm for AP$.$ What does it mean that the greedy algo$-$

rithm for $AP$ is of domination number $1?$

Prove that the greedy algorithm for $AP$ is of domination number $1.$

Run the Greedy Algorithm on the instance of the STSP given in Figure $1.$ Show

in which order the algorithm picks the edges for the tour. Now run the Insertion

Algorithm on this instance of the STSP starting from subtour ABCA and inserting

first $D$ and then $E.$ Which subtour do we obtain after inserting $D$ and which tour

do we obtain after inserting $E?$ Justify your answers.

$($i$)$ Describe the Backtracking and Jumptracking strategies for branching $($to solve

Integer Programming problems$).($ii$)$ Describe at least one advantage and one

disadvantage of each of the two strategies.

Find the optimal value of $z$ using branch$-$and$-$bound:

$\{\begin{array}{ccc}\text{:}[& \text{m}\text{i}\text{n}\text{i}\text{m}\text{i}\text{z}\text{e},& z=-10x_1-8x_2-7x_3-10x_4]\\ & \text{s}\text{u}\text{b}\text{j}\text{e}\text{c}\text{t}to,& -2x_1-2x_2-4x_3-5x_4\\ ,& x_1,x_2,x_3,x_4=0or& 1\end{array}-8$

Give an outline $($pseudocode$)$ of the STSP double tree heuristic $($DTH$)$ for the

Symmetric Travelling Salesman Problem.

Consider an instance of the STSP with distance matrix

$\left[\begin{array}{cccc}0& 3& 14\mathrm{.}8& 17\\ 3& 0& 5& 8\\ 14\mathrm{.}8& 5& 0& 18\mathrm{.}4\\ 17& 8& 18\mathrm{.}4& 0\end{array}\right]$

$($a$)$ Find a tour using DTH$.($b$)$ Find a tour using Christofides' heuristic.