Implement def k$\_$tsp$\_$mtz$\_$encoding$($n$,$ k$,$ cost$\_$matrix$)$: 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.

use the following setup:

$-$ Decision variables $x$\_\{$i$,$j$\}$$ for $i

ot$=$ j$ denoting that the tour traverses the edge from $i$ to $j$$.$

$-$ Time stamps $t$\_1,\backslash$ldots$,$ t$\_\{$n$-1\}$$$.$ The start$/$end vertex $$0$$ does not get a time stamp.

the code must obey the following degree constraints:

$-$ Vertex $0$: $k$ edges leave and $k$ edges enter.

$-$ Vertex $1,...,$ n$-1$: $1$ edge leaves and $1$ edge enters $($same as TSP$).$

Formulate the timestamp constraints

Your code must return a list $`$lst$`$ that has exactly $k$ lists in it$,$ wherein $`$lst$[$j$]`$ represents the locations visited by the $j$^\{$th$\}$$ salesperson. The tour must start with vertex $0$

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

Must pass the following test cases:

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'

print$(\text{'}$test passed'$)$

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$=3$

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 $-16)<=0\mathrm{.}001,$ f'Expected tour cost is $16,$ 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'

print$(\text{'}$test passed'$)$