Complete the implementation of the function k$\_$tsp$\_$mtz$\_$encoding$($n$,$ k$,$ cost$\_$matrix$)$ below using PULP. It follows the same input convention as the code supplied in the notes. The input n denotes the size of the graph with vertices labeled $0,..,$ n$-1,$ k is the number of salespeople, and cost$\_$matrix is a list of lists wherein cost$\_$matrix$[$i$][$j$]$ is the edge cost to go from i to j for i $!=$ j$.$ Your code must avoid accessing cost$\_$matrix$[$i$][$i$]$ to avoid bugs. These entries will be supplied as None in the test cases.

Your code must return a list lst that has exactly k

lists in it$,$ wherein lst$[$j$]$ represents the locations visited by the jth

salesperson.

For the example above, for k$=2$

$,$ your code must return

$[[0,2,1,4],[0,3]]$

For the example above, for k$=3$

$,$ your code must return

$[[0,1,4],[0,2],[0,3]]$from pulp import $*$

def k$\_$tsp$\_$mtz$\_$encoding$($n$,$ k$,$ cost$\_$matrix$)$:

# check inputs are OK

assert $1<=$ k $<$ n

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{'}$

prob $=$ LpProblem$(\text{'}$kTSP$\text{'},$ LpMinimize$)$

# finish your implementation here

# your code must return a list of k$-$lists $[[0,$ i$1,...,$ il$],[0,$ j$1,...,$jl$],...]$ wherein

# the ith entry in our list of lists represents the

# tour undertaken by the ith salesperson

# your code here

raise NotImplementedError

Test case:

cost$\_$matrix$=[[$None$,3,4,3,5],$

$[1,$ None, $2,4,1],$

$[2,1,$ None, $5,4],$

$[1,1,5,$ None, $4],$

$[2,1,3,5,$ None$]]$

n$=5$

k$=2$

all$\_$tours $=$ k$\_$tsp$\_$mtz$\_$encoding$($n$,$ k$,$ cost$\_$matrix$)$

print$($f$\text{'}$Your code returned tours: $\{$all$\_$tours$\}\text{'})$

assert len$($all$\_$tours$)==$ k$,$ f$\text{'}$k$=\{$k$\}$ must yield two tours $--$ your code returns $\{$len$($all$\_$tours$)\}$ tours instead'

tour$\_$cost $=0$

for tour in all$\_$tours:

assert tour$[0]==0,$ 'Each salesperson tour must start from vertex $0\text{'}$

i $=0$

for j in tour$[1$:$]$:

tour$\_$cost $+=$ cost$\_$matrix$[$i$][$j$]$

i $=$ j

tour$\_$cost $+=$ cost$\_$matrix$[$i$][0]$

print$($f$\text{'}$Tour cost obtained by your code: $\{$tour$\_$cost$\}\text{'})$

assert abs$($tour$\_$cost $-12)<=0\mathrm{.}001,$ f'Expected tour cost is $12,$ your code returned $\{$tour$\_$cost$\}\text{'}$

for i in range$(1,$ n$)$:

is$\_$in$\_$tour $=[1$ if i in tour else $0$ for tour in all$\_$tours$]$

assert sum$($is$\_$in$\_$tour$)==1,$ f$\text{'}$ vertex $\{$i$\}$ is in $\{$sum$($is$\_$in$\_$tour$)\}$ tours $--$ this is incorrect'

Please run above test case