In this problem, we wish to solve TSP with additional constraints. Suppose we are given a TSP instance in the form of a $\backslash$times $$

matrix $$

representing a complete graph.

We wish to solve a TSP but with additional constraints specified as a list $[(0,0),...,(,)]$

wherein each pair $(,)$

in the list specifies that vertex $$

must be visited in the tour before vertex $$

$.$ Assume that the tour starts$/$ends at vertex $0$

and none of the vertices in the constraint list is $0$

$.$ I.e$,!=0,!=0$

for all $0<=<=$

$.$

Modify one of the ILP encodings we have presented to solve TSP with extra constraints. Implement your solution in the function tsp$\_$with$\_$extra$\_$constraints$($n$,$ cost$\_$matrix, constr$\_$list$)$ where the extra argument constr$\_$list is a list of pairs $[($i$0,$j$0),....,($ik$,$ jk$)]$ that specify for each pair $($il$,$jl$)$ that vertex il must be visited before jl$.$ Assume that the problem is feasible $($no need to handle infeasible instances$).$ Your code should output the optimal tour as a list.

Example

Consider again the graph with $5$

nodes and the following cost matrix from problem $1$:

The optimal TSP tour will be $[0,3,1,4,2]$

with total cost $10$

$.$

Suppose we added the constraints $[(4,3),(1,2)]$

we note that the tour satisfies the constraint $(1,2)$

since it visits vertex $1$

before vertex $2$

but it unfortunately, $(4,3)$

is violated since vetex $3$

is visited before $4$

in the tour.def tsp$\_$with$\_$extra$\_$constraints$($n$,$ cost$\_$matrix, constraints$)$:

assert len$($cost$\_$matrix$)==$ n$,$ f'Cost matrix is not $\{$n$\}$x$\{$n$\}\text{'}$

assert all$($len$($cj$)==$ n for cj in cost$\_$matrix$),$ f'Cost matrix is not $\{$n$\}$x$\{$n$\}\text{'}$

assert all$(1<=$ i $<$ n and $1<=$ j $<$ n and i $!=$ j for $($i$,$j$)$ in constraints$)$

# TODO: encode the problem in pulp $($a$)$ decision variables; $($b$)$ constraints; $($c$)$ objective; $($d$)$ solve and extract

# solution. This is going to be very close to the MTZ encoding that we have presented in our notes. You can use

# our code as a starting point.

# your code here

raise NotImplementedError