TSPExample

[Advanced] TSP: The heuristic with subtour elimination constraints

---

As we did previously, we will asume we are in the Examples folder (if it is not the case, all the paths must be modified relatively). In this case, we also import the Cuts and ConComp (connected components) module, the Cut class and the function getSubsets respectively, the latter is used to get all connected components of a graph.

import sys
import os
sys.path.append(os.path.pardir)
sys.path.append(os.path.join(os.path.pardir, 'Instances'))
import TSP as TSP
from Neighborhood import Neighborhoods, varClusterFromMPS
from VMND import solver
from Cuts import Cut
from ConComp import getSubsets

As we did in the MVRPD example, we will skip all the coding of the model, and we will asume we have a mps file with the formulation of the TSP with all its constraints except those concerning the subtour elimination. The binary routing variables will have the names 'x_i_j' (with i < j) which represent each unidirected edge (i, j).

In the code below, we set the amount of nodes, we generate randomly (with fixed seed) a TSP instance and we export the generated mps file into the usual MIPLIB folder. Finally the path is saved into a string variable.

nodes = 60
tspInst = TSP.TSP(nodes)
tspInst.exportMPS()

pathTSPInst = tspInst.pathMPS

Then, we generate the Neighborhoods through the varaible cluster as we have seen before in the arbitrary MIP example. Of course, we could have generated differently, in fact something very similar to the k nearest neighbors used in the MVRPD example is already implemented in the TSP module.

nbhs = varClusterFromMPS(pathTSPInst, numClu = 5, varFilter = None)

The following step is something we have not exemplified enough yet, this is, the creation of a subtour elimination (separation) function. This function is embedded in the Branch and Cut procedure through a gurobi Callback

def sepFunctionTSP(solValues):

    # List of cuts to add, initialized as empty.
    cuts = []

    # The keys of the dictionary are formated to tuple (string 'x', int i, int j).
    solValues = { (key.split('_')[0], int(key.split('_')[1]), int(key.split('_')[2]) ) : solValues[key] for key in solValues.keys()}
    
    # the graph is created by the active edges.
    edges = []
    for i in range(nodes):
        for j in range(nodes):
            if i < j:
                # The numeric threshold was set to be 0.99.
                if solValues[('x', i, j)] >= 0.99:
                    edges.append((i, j))

    # The function returning the connected components as a list of lists of integers.
    subsets = getSubsets(edges, nodes)

    if len(edges) > 0:
        for subset in subsets:

            # The new cut is created.
            newCut = Cut()
            nonzeros = {}

            nonzeros.update({ 'x_{}_{}'.format(i, j) : 1 for i in subset for j in subset if i < j })
            newCut.nonzero = nonzeros

            newCut.sense = '<='

            newCut.rhs = len(subset) - 1

            cuts.append(newCut)
    return cuts

Let's recall that the classic subtour elimination constraint:

Classic TSP Subtour Elimination Constraint

can be seen in the code above, in which the coefficient is 1 for every variable associated to edges inside the subset. Also, the length of the list subsets is obviously the cardinality of the set. For further information about the __Cut__ class see the [Modules](Documentation).

Finally, we run the solver from module VMND.py, this time the inputs addlazy needs to be True and the funlazy is set to the previously defined separation function:

solver(
    pathTSPInst,
    verbose = True,
    addlazy= True,
    funlazy = sepFunctionTSP,
    importNeighborhoods=True,
    importedNeighborhoods= nbhs,
    funTest= None,
    callback = 'vmnd',
    alpha = 1,
    minBCTime= 4,
    timeLimitSeconds= None
)

Needless to say, this separation function can be directly set from the module TSP.py can be set straightforwardly set with the method genLazy(), as we can see in the code below:

tspInst.run()

As the seed is set, the objective function and solution are the same. Also, a nice matplotlib visualization of the routes, based on the coordinates of the randomly generated points:

tspInst.visualizeRes()