TSP: k$\_$tsp$\_$mtz$\_$encoding$()$:

I set up an LP problem with PULP to solve this TSP optimization, but the answers Im getting are suboptimal. What is the cause of the issue?

Complete the implementation of the function k$\_$tsp$\_$mtz$\_$encoding$($n$,$ k$,$ cost$\_$matrix$)$ below. 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 $$

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

salesperson.

For the example above, for $=2$

$,$ your code must return

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

For the example above, for $=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 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

# variables for each edge

x $=\{($i$,$ j$,$ p$)$: LpVariable$($f$\text{'}$x$\_\{$i$\}\_\{$j$\}\_\{$p$\}\text{'},$ cat$=$'Binary'$)$

for i in range$($n$)$ for j in range$($n$)$ for p in range$($k$)\}$

# Objective function: minimize the total cost

prob $+=$ lpSum$($cost$\_$matrix$[$i$][$j$]*$ x$[($i$,$ j$,$ p$)]$

for i in range$($n$)$ for j in range$($n$)$ if i $!=$ j for p in range$($k$))$

# constraints:each city is visited exactly once by exactly one salesperson

# ensure that each salesperson begins and ends at vertex $0$

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

prob $+=$ lpSum$($x$[($i$,$ j$,$ p$)]$ for j in range$($n$)$ if i $!=$ j for p in range$($k$))==1$

prob $+=$ lpSum$($x$[($j$,$ i$,$ p$)]$ for j in range$($n$)$ if i $!=$ j for p in range$($k$))==1$

for p in range$($k$)$:

prob $+=$ lpSum$($x$[(0,$ j$,$ p$)]$ for j in range$(1,$ n$))==1$

prob $+=$ lpSum$($x$[($j$,0,$ p$)]$ for j in range$(1,$ n$))==1$

# Subtour elimination constraints using mtz

u $=\{$i: LpVariable$($f$\text{'}$u$\_\{$i$\}\text{'},$ lowBound$=0,$ upBound$=$n$-1,$ cat$=$'Integer'$)$ for i in range$($n$)\}$

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

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

if i $!=$ j:

for p in range$($k$)$:

#here is the actual mtz logic

prob $+=$ u$[$i$]-$ u$[$j$]+($n $-1)*$ x$[($i$,$ j$,$ p n $-2$

# Solve the problem

prob.solve$()$

# Extract the solution

tours $=[[]$ for $\_$ in range$($k$)]$

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

for j in range$($n$)$:

for p in range$($k$)$:

if x$[($i$,$ j$,$ p$)].$varValue $==1$:

tours$[$p$].$append$($i$)$

break

return tours

$$

Attached is a screenshot of the failing test case