Travelling Salesman Problem with subtour elimination

Description: this example shows how to solve a TSP by eliminating subtours using amplpy and ampls

Tags: callbacks, tsp

Notebook author: Christian Valente <christian.valente@gmail.com>

Model author: N/A

import os

if not os.path.isdir("tsp_inputs"):
    os.system("git clone https://github.com/ampl/colab.ampl.com.git")
    os.chdir("colab.ampl.com/authors/mapgccv/callbacks")

Setup and cloud integration

# Install dependencies
%pip install -q amplpy amplpy-gurobi amplpy-cplex
%pip install -q tsplib95 matplotlib pandas

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["coin"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Options

import os

USE_CALLBACKS = True
PLOTSUBTOURS = True
TSP_FILE = "./tsp_inputs/a280.tsp"

Imports

SOLVER = "gurobi"
SOLVER_OPTIONS = ["outlev=1"]
# Import utilities
from amplpy import AMPL  # pip install amplpy

if SOLVER == "gurobi":
    import amplpy_gurobi as ampls  # pip install amplpy-gurobi
elif SOLVER == "cplex":
    import amplpy_cplex as ampls  # pip install amplpy-cplex
elif SOLVER == "xpress":
    import amplpy_xpress as ampls  # pip install amplpy-gurobi
import tsplib95 as tsp  # pip install tsplib95
import matplotlib.pyplot as plt  # pip install matplotlib
import matplotlib.colors as colors
from time import time
import pandas as pd

plt.rcParams["figure.dpi"] = 200

Define TSP model in AMPL

We are using amplpy to define the subtour elimination constraint in AMPL and instantiating it appropriately and ampls to add cuts directly from the solver callback.

%%ampl
set NODES ordered;
param hpos {NODES};
param vpos {NODES};

set PAIRS := {i in NODES, j in NODES: ord(i) < ord(j)};

param distance {(i,j) in PAIRS}
   := sqrt((hpos[j]-hpos[i])**2 + (vpos[j]-vpos[i])**2);

var X {PAIRS} binary;

minimize Tour_Length: sum {(i,j) in PAIRS} distance[i,j] * X[i,j];

subject to Visit_All {i in NODES}:
   sum {(i, j) in PAIRS} X[i,j] + sum {(j, i) in PAIRS} X[j,i] = 2;

Function to load TSP data files and return a dictionary of (nodeid : coordinate)

def getDictFromTspFile(tspFile):
    p = tsp.load(tspFile)
    if not p.is_depictable:
        print("Problem is not depictable!")

    # Amendments as we need the nodes lexographically ordered
    nnodes = len(list(p.get_nodes()))
    i = 0
    while nnodes > 1:
        nnodes = nnodes / 10
        i += 1
    formatString = f"{{:0{i}d}}"
    nodes = {
        formatString.format(value): p.node_coords[index + 1]
        for index, value in enumerate(p.get_nodes())
    }
    return nodes

Create AMPL object with amplpy and load model and data

# Get the model from the cell above
tsp_model = _ampl_cells[0]

# Load model in AMPL
ampl = AMPL()
ampl.eval(tsp_model)
ampl.option["solver"] = SOLVER
ampl.option[SOLVER + "_options"] = " ".join(SOLVER_OPTIONS)

# Set problem data from tsp file
nodes = getDictFromTspFile(TSP_FILE)
df = pd.DataFrame.from_dict(nodes, orient="index", columns=["hpos", "vpos"])
df.index.name = "NODES"
ampl.set_data(df, "NODES")

# Set some globals that never change during the execution of the problem
NODES = set(nodes.keys())
CPOINTS = {
    node: complex(coordinate[0], coordinate[1]) for (node, coordinate) in nodes.items()
}

Define some helpers functions to plot the tours

def plotTours(tours: list, points_coordinate: dict):
    # Plot all the tours in the list each with a different color
    colors = ["b", "g", "c", "m", "y", "k"]
    for i, tour in enumerate(tours):
        tourCoordinates = [points_coordinate[point.strip("'")] for point in tour]
        color = colors[i % len(colors)]
        plot_all(tourCoordinates, color=color)
    plt.show()


def plot_all(tour, alpha=1, color=None):
    # Plot the tour as blue lines between blue circles
    plotline(list(tour) + [tour[0]], alpha=alpha, color=color)
    plotline([tour[0]], "s", alpha=alpha, color=color)


def plotline(points, style="o-", alpha=1, color=None):
    "Plot a list of points (complex numbers) in the 2-D plane."
    X, Y = XY(points)
    if color:
        plt.plot(X, Y, style, alpha=alpha, color=color)
    else:
        plt.plot(X, Y, style, alpha=alpha)


def XY(points):
    "Given a list of points, return two lists: X coordinates, and Y coordinates."
    return [p.real for p in points], [p.imag for p in points]

Define some helper functions to help with the graphs (e.g. get the subtour given a set of arcs)

# Graphs helper routines
def trasverse(node, arcs: set, allnodes: set, subtour=None) -> list:
    # Trasverses all the arcs in the set arcs, starting from node
    # and returns the tour
    if not subtour:
        subtour = list()
    # Find arcs involving the current node
    myarcs = [(i, j) for (i, j) in arcs if node == i or node == j]
    if len(myarcs) == 0:
        return
    # Append the current node to the current subtour
    subtour.append(node)

    # Use the first arc found
    myarc = myarcs[0]
    # Find destination (or origin) node
    destination = next(i for i in myarc if i != node)
    # Remove from arcs and nodes to visit
    arcs.remove(myarc)
    if node in allnodes:
        allnodes.remove(node)

    trasverse(destination, arcs, allnodes, subtour)
    return subtour


def findSubTours(arcs: set, allnodes: set):
    """Find all the subtours defined by a set of arcs and
    return them as a list of list
    """
    subtours = list()
    allnodes = allnodes.copy()
    while len(allnodes) > 0:
        l = trasverse(next(iter(allnodes)), arcs, allnodes)
        subtours.append(l)
    return subtours

AMPLPY implementation of sub-tours elimination

def amplSubTourElimination(ampl: AMPL):
    # Add the constraint and the needed parameters
    subToursAMPL = """param nSubtours >= 0 integer, default 0;
    set SUB {1..nSubtours} within NODES;

    subject to Subtour_Elimination {k in 1..nSubtours}:
    sum {i in SUB[k], j in NODES diff SUB[k]}
    if (i, j) in PAIRS then X[i, j] else X[j, i] >= 2;"""
    ampl.eval(subToursAMPL)

    nSubtoursParam = ampl.get_parameter("nSubtours")
    SubtoursSet = ampl.get_set("SUB")

    allsubtours = list()
    while True:  # Repeat until the solution contains only one tour
        ampl.solve()
        # Get solution
        ARCS = ampl.get_data("{(i,j) in PAIRS : X[i,j] > 0} X[i,j];")
        ARCS = set([(i, j) for (i, j, k) in ARCS.toList()])
        subtours = findSubTours(ARCS, NODES)
        # If we have only one tour, the solution is valid
        if len(subtours) <= 1:
            break
        print(f"Found {len(subtours)} subtours, plotting them and adding cuts")
        if PLOTSUBTOURS:
            plotTours(subtours, CPOINTS)
        # Else add the current tours to the list of subtours
        allsubtours.extend(subtours)
        # And add those to the constraints by assigning the values to
        # the parameter and the set
        nSubtoursParam.set(len(allsubtours))
        for i, tour in enumerate(allsubtours):
            SubtoursSet[i + 1].set_values(tour)

ampls callbacks implementation of subtours elimination

# Callback class that actually add the cuts if subtours are found in a solution
class MyCallback(ampls.GenericCallback):
    def __init__(self):
        # Constructor, simply sets the iteration number to 0
        super().__init__()
        self.iteration = 0

    def run(self):
        try:
            # For each solution
            if self.getAMPLWhere() == ampls.Where.MIPSOL:
                self.iteration += 1
                print(f"\nIteration {self.iteration}: Finding subtours")
                sol = self.getSolutionVector()
                arcs = [xvars[i] for i, value in enumerate(sol) if value > 0]
                subTours = findSubTours(set(arcs), set(vertices))
                if len(subTours) == 1:
                    print("No subtours detected. Not adding any cut")
                    return 0
                print(f"Adding {len(subTours)} cuts")
                if PLOTSUBTOURS:
                    plotTours(subTours, CPOINTS)
                for subTour in subTours:
                    st1 = set(subTour)
                    nst1 = set(vertices) - st1
                    externalArcs = [
                        (i, j) if i < j else (j, i) for i in st1 for j in nst1
                    ]
                    varsExternalArcs = [xinverse[i, j] for (i, j) in externalArcs]
                    coeffs = [1 for i in range(len(varsExternalArcs))]
                    if PLOTSUBTOURS:
                        print("Adding cut for subtour:", st1)
                    self.addLazyIndices(
                        varsExternalArcs, coeffs, ampls.CutDirection.GE, 2
                    )
                    if len(subTours) == 2:
                        return 0
                print("Continue solving")
            return 0
        except Exception as e:
            print("Error:", e)
            return 1

# Global variables to store entities needed by the callbacks
# that never change
xvars = None
xinverse = None
vertices = None


def solverSubTourElimination(ampl: AMPL, solver, solver_options):
    global xvars, xinverse, vertices
    # Export the model using ampls
    model = ampl.to_ampls(solver, solver_options)
    model.enableLazyConstraints()

    # Get the global maps between solver vars and AMPL entities
    varMap = model.getVarMapFiltered("X")
    # print("varMap:", varMap)
    inverse = model.getVarMapInverse()
    xvars = {index: ampls.var2tuple(var)[1:] for var, index in varMap.items()}
    xinverse = {ampls.var2tuple(var)[1:]: index for index, var in inverse.items()}
    vertices = list(
        sorted(set([x[0] for x in xvars.values()] + [x[1] for x in xvars.values()]))
    )

    # Assign the callback
    callback = MyCallback()
    model.set_callback(callback)
    print("Start optimization")
    # Start the optimization
    model.optimize()
    # Import the solution back to AMPL
    ampl.import_solution(model)

Script running the optimization

t0 = time()
if not USE_CALLBACKS:
    amplSubTourElimination(ampl)
else:
    solverSubTourElimination(ampl, SOLVER, SOLVER_OPTIONS)

Start optimization

Iteration 1: Finding subtours
Adding 5 cuts

Adding cut for subtour: {'089', '127', '252', '088', '196', '039', '192', '098', '218', '031', '124', '121', '012', '066', '045', '023', '025', '038', '212', '097', '237', '062', '071', '172', '270', '096', '219', '040', '259', '058', '111', '244', '197', '036', '238', '154', '188', '240', '140', '273', '222', '151', '167', '194', '001', '087', '236', '003', '019', '024', '079', '280', '072', '226', '160', '175', '022', '109', '020', '067', '110', '070', '050', '182', '275', '044', '147', '201', '263', '228', '061', '076', '060', '026', '035', '138', '170', '260', '037', '239', '198', '266', '029', '106', '249', '055', '074', '007', '278', '131', '028'}
Adding cut for subtour: {'171', '276', '130', '102', '184', '082', '049', '103', '030', '125', '169', '274', '217', '165', '248', '101', '235', '262', '021', '146'}
Adding cut for subtour: {'203', '005', '100', '209', '241', '205', '269', '141', '271', '245', '257', '225', '199', '052', '264', '180', '134', '090', '002', '114', '161', '094', '065', '078', '164', '168', '157', '190', '008', '250', '027', '085', '221', '133', '277', '265', '247', '115', '063', '123', '118', '202', '093', '206', '261', '178', '176', '211', '047', '159', '105', '075', '246', '051', '117', '173', '129', '186', '153', '112', '099', '144', '272', '011', '073', '004', '174', '006', '018', '148', '229', '195', '135', '069', '119', '231', '234', '034', '242', '095', '017', '009', '255', '256', '227', '104', '137', '042', '081', '010', '210', '013', '214', '187', '230', '043', '158', '126', '083', '216', '113', '116', '142', '080', '268', '086', '091', '232', '189', '181', '193', '150', '223', '155', '243', '120', '046', '162', '064', '204', '015', '107', '077', '191', '200', '033', '054', '224', '108', '267', '233', '032', '156', '053', '048', '092', '220', '149', '207', '041', '215', '059', '056', '128', '279', '014', '136'}
Adding cut for subtour: {'163', '253', '145', '258'}
Adding cut for subtour: {'208', '057', '152', '132', '185', '068', '166', '016', '084', '254', '143', '213', '179', '139', '122', '183', '251', '177'}
Continue solving

Iteration 2: Finding subtours
Adding 70 cuts

Adding cut for subtour: {'089', '090', '192', '191'}
Adding cut for subtour: {'127', '154', '153', '128'}
Adding cut for subtour: {'172', '171', '110', '109'}
Adding cut for subtour: {'030', '251', '029', '252'}
Adding cut for subtour: {'006', '276', '275', '005'}
Adding cut for subtour: {'088', '193', '087', '194'}
Adding cut for subtour: {'210', '071', '209', '072'}
Adding cut for subtour: {'075', '205', '206', '076'}
Adding cut for subtour: {'129', '130', '151', '152'}
Adding cut for subtour: {'139', '141', '140', '142'}
Adding cut for subtour: {'272', '010', '009', '271'}
Adding cut for subtour: {'036', '246', '035', '245'}
Adding cut for subtour: {'056', '055', '225', '226'}
Adding cut for subtour: {'229', '052', '230', '051'}
Adding cut for subtour: {'263', '018', '264', '017'}
Adding cut for subtour: {'101', '179', '180', '102'}
Adding cut for subtour: {'134', '147', '148', '133'}
Adding cut for subtour: {'161', '162', '119', '120'}
Adding cut for subtour: {'183', '098', '097', '184'}
Adding cut for subtour: {'123', '124', '157', '158'}
Adding cut for subtour: {'092', '091', '189', '190'}
Adding cut for subtour: {'257', '024', '023', '258'}
Adding cut for subtour: {'254', '027', '028', '253'}
Adding cut for subtour: {'086', '085', '195', '196'}
Adding cut for subtour: {'122', '160', '121', '159'}
Adding cut for subtour: {'222', '221', '059', '060'}
Adding cut for subtour: {'248', '034', '247', '033'}
Adding cut for subtour: {'215', '216', '065', '066'}
Adding cut for subtour: {'003', '278', '277', '004'}
Adding cut for subtour: {'267', '268', '013', '014'}
Adding cut for subtour: {'208', '074', '207', '073'}
Adding cut for subtour: {'235', '045', '236', '046'}
Adding cut for subtour: {'080', '079', '201', '202'}
Adding cut for subtour: {'187', '093', '188', '094'}
Adding cut for subtour: {'043', '044', '238', '237'}
Adding cut for subtour: {'062', '219', '061', '220'}
Adding cut for subtour: {'057', '224', '058', '223'}
Adding cut for subtour: {'104', '178', '103', '177'}
Adding cut for subtour: {'185', '186', '095', '096'}
Adding cut for subtour: {'270', '011', '012', '269'}
Adding cut for subtour: {'176', '175', '106', '105'}
Adding cut for subtour: {'260', '022', '021', '259'}
Adding cut for subtour: {'112', '111', '170', '169'}
Adding cut for subtour: {'117', '164', '118', '163'}
Adding cut for subtour: {'068', '213', '214', '067'}
Adding cut for subtour: {'174', '108', '107', '173'}
Adding cut for subtour: {'099', '100', '182', '181'}
Adding cut for subtour: {'084', '197', '198', '083'}
Adding cut for subtour: {'168', '167', '113', '114'}
Adding cut for subtour: {'261', '019', '262', '020'}
Adding cut for subtour: {'146', '135', '136', '145'}
Adding cut for subtour: {'211', '212', '069', '070'}
Adding cut for subtour: {'232', '231', '050', '049'}
Adding cut for subtour: {'001', '280', '002', '279'}
Adding cut for subtour: {'144', '143', '138', '137'}
Adding cut for subtour: {'255', '025', '026', '256'}
Adding cut for subtour: {'156', '126', '125', '155'}
Adding cut for subtour: {'081', '199', '082', '200'}
Adding cut for subtour: {'054', '228', '227', '053'}
Adding cut for subtour: {'233', '234', '048', '047'}
Adding cut for subtour: {'239', '041', '240', '042'}
Adding cut for subtour: {'063', '064', '218', '217'}
Adding cut for subtour: {'165', '115', '116', '166'}
Adding cut for subtour: {'031', '250', '249', '032'}
Adding cut for subtour: {'204', '203', '077', '078'}
Adding cut for subtour: {'039', '241', '242', '040'}
Adding cut for subtour: {'274', '008', '273', '007'}
Adding cut for subtour: {'266', '016', '015', '265'}
Adding cut for subtour: {'038', '037', '243', '244'}
Adding cut for subtour: {'132', '150', '131', '149'}
Continue solving

Iteration 3: Finding subtours
Adding 19 cuts

Adding cut for subtour: {'089', '127', '005', '088', '100', '130', '141', '271', '196', '039', '199', '166', '082', '180', '134', '090', '161', '065', '078', '164', '168', '030', '125', '031', '157', '008', '124', '027', '121', '012', '133', '277', '066', '139', '101', '123', '063', '023', '025', '038', '118', '062', '071', '152', '178', '270', '176', '040', '159', '075', '111', '145', '129', '122', '163', '186', '153', '112', '169', '099', '197', '144', '179', '011', '036', '073', '004', '154', '006', '273', '140', '148', '018', '151', '167', '195', '021', '194', '135', '119', '069', '034', '003', '017', '019', '009', '024', '079', '072', '137', '042', '081', '010', '013', '187', '043', '158', '126', '083', '160', '175', '022', '080', '268', '091', '177', '109', '020', '067', '110', '070', '150', '155', '016', '120', '201', '162', '064', '015', '077', '061', '076', '200', '033', '060', '026', '035', '108', '267', '138', '032', '156', '037', '092', '198', '149', '274', '041', '165', '029', '132', '068', '074', '128', '007', '279', '278', '131', '014', '136', '028'}
Adding cut for subtour: {'172', '171', '170'}
Adding cut for subtour: {'252', '209', '263', '255', '219', '211', '256', '228', '259', '227', '257', '225', '226', '264', '224', '254', '210', '213', '214', '260', '230', '218', '250', '258', '220', '216', '221', '207', '265', '217', '251', '215', '208', '222', '248', '249', '229', '262', '253', '212', '261', '223'}
Adding cut for subtour: {'266', '203', '205', '202', '206', '204'}
Adding cut for subtour: {'243', '241', '247', '240', '244', '242', '245'}
Adding cut for subtour: {'052', '050', '051', '049', '053', '048'}
Adding cut for subtour: {'093', '095', '096', '094', '098', '097'}
Adding cut for subtour: {'188', '269', '189', '190'}
Adding cut for subtour: {'087', '115', '084', '113', '116', '085', '117', '114', '086'}
Adding cut for subtour: {'045', '054', '055', '056', '046', '047'}
Adding cut for subtour: {'232', '239', '246', '238', '231', '237'}
Adding cut for subtour: {'057', '044', '059', '058'}
Adding cut for subtour: {'181', '184', '185', '272', '182', '183'}
Adding cut for subtour: {'104', '276', '105', '103', '102'}
Adding cut for subtour: {'106', '173', '174', '107', '275'}
Adding cut for subtour: {'233', '235', '234', '236'}
Adding cut for subtour: {'001', '280', '002'}
Adding cut for subtour: {'146', '147', '143', '142'}
Adding cut for subtour: {'193', '192', '191'}
Continue solving

Iteration 4: Finding subtours
Adding 8 cuts

Adding cut for subtour: {'089', '127', '171', '005', '088', '100', '130', '271', '039', '166', '052', '082', '090', '114', '161', '094', '065', '098', '078', '168', '030', '125', '031', '157', '190', '008', '124', '027', '085', '012', '133', '277', '121', '066', '045', '101', '115', '123', '063', '023', '025', '038', '118', '093', '097', '062', '057', '071', '152', '172', '178', '185', '176', '096', '047', '040', '159', '058', '105', '075', '111', '051', '117', '173', '129', '122', '163', '186', '153', '112', '169', '099', '272', '011', '036', '073', '004', '154', '188', '174', '006', '273', '018', '151', '167', '021', '119', '069', '034', '087', '276', '095', '017', '019', '009', '024', '102', '079', '104', '072', '042', '081', '010', '013', '103', '187', '043', '158', '126', '083', '160', '175', '022', '113', '116', '080', '086', '091', '177', '109', '020', '189', '181', '067', '110', '070', '050', '182', '275', '155', '044', '016', '120', '046', '162', '064', '015', '107', '077', '061', '076', '033', '184', '054', '060', '026', '035', '108', '049', '170', '032', '156', '053', '048', '037', '092', '274', '041', '165', '029', '106', '059', '056', '055', '132', '068', '074', '084', '128', '007', '131', '014', '028', '183'}
Adding cut for subtour: {'203', '252', '209', '147', '143', '205', '201', '263', '255', '141', '211', '204', '256', '219', '259', '196', '257', '137', '227', '228', '225', '200', '199', '226', '264', '224', '145', '254', '267', '210', '138', '213', '214', '260', '230', '218', '197', '198', '250', '258', '144', '216', '220', '142', '221', '207', '265', '139', '202', '217', '251', '215', '208', '266', '140', '222', '249', '229', '262', '195', '146', '194', '253', '212', '206', '261', '223'}
Adding cut for subtour: {'240', '232', '236', '243', '239', '235', '246', '241', '237', '233', '247', '238', '231', '234', '244', '242', '245'}
Adding cut for subtour: {'193', '180', '191', '192', '179', '164'}
Adding cut for subtour: {'270', '136', '134', '135', '269', '268'}
Adding cut for subtour: {'149', '150', '148'}
Adding cut for subtour: {'001', '280', '002', '003'}
Adding cut for subtour: {'278', '279', '248'}
Continue solving

Iteration 5: Finding subtours
Adding 12 cuts

Adding cut for subtour: {'089', '171', '088', '100', '039', '166', '082', '090', '114', '161', '065', '094', '098', '078', '164', '168', '030', '125', '031', '157', '124', '121', '085', '066', '101', '123', '063', '115', '038', '118', '093', '097', '062', '071', '172', '096', '040', '159', '075', '111', '117', '122', '163', '112', '169', '099', '036', '073', '167', '119', '069', '034', '087', '095', '102', '079', '072', '042', '081', '043', '158', '083', '160', '175', '113', '116', '080', '086', '091', '109', '067', '110', '070', '120', '162', '064', '077', '061', '076', '033', '060', '035', '108', '170', '032', '037', '092', '041', '165', '068', '074', '084'}
Adding cut for subtour: {'127', '203', '005', '241', '205', '130', '269', '271', '196', '245', '257', '225', '264', '180', '134', '192', '002', '218', '190', '008', '250', '258', '027', '221', '012', '247', '133', '265', '277', '023', '025', '202', '212', '206', '261', '152', '178', '185', '270', '176', '211', '219', '259', '246', '254', '213', '129', '244', '186', '153', '197', '272', '179', '011', '238', '004', '154', '188', '240', '006', '222', '018', '273', '151', '229', '262', '195', '021', '194', '135', '231', '242', '001', '276', '003', '017', '009', '024', '255', '280', '256', '227', '137', '226', '010', '210', '013', '214', '187', '230', '126', '216', '022', '268', '251', '177', '189', '181', '193', '150', '182', '223', '155', '275', '243', '016', '201', '263', '204', '191', '228', '015', '184', '026', '224', '267', '138', '156', '260', '239', '198', '220', '207', '274', '217', '215', '266', '029', '248', '249', '128', '007', '279', '278', '014', '136', '028', '183'}
Adding cut for subtour: {'208', '209', '252', '253'}
Adding cut for subtour: {'140', '148', '146', '147', '143', '142', '149', '139', '141'}
Adding cut for subtour: {'051', '052', '050', '049'}
Adding cut for subtour: {'057', '044', '059', '045', '058', '056'}
Adding cut for subtour: {'232', '236', '235', '233', '234', '237'}
Adding cut for subtour: {'104', '103', '105'}
Adding cut for subtour: {'106', '107', '174', '173'}
Adding cut for subtour: {'132', '019', '020', '131'}
Adding cut for subtour: {'054', '055', '046', '053', '048', '047'}
Adding cut for subtour: {'199', '145', '200', '144'}
Continue solving

Iteration 6: Finding subtours
Adding 6 cuts

Adding cut for subtour: {'089', '171', '088', '100', '039', '166', '082', '090', '114', '161', '065', '094', '098', '078', '164', '168', '030', '125', '031', '157', '124', '121', '085', '066', '101', '123', '063', '115', '038', '118', '093', '097', '062', '071', '172', '096', '040', '159', '105', '075', '111', '117', '173', '122', '163', '112', '169', '099', '036', '073', '174', '167', '119', '069', '034', '087', '095', '102', '079', '104', '072', '042', '081', '103', '043', '158', '083', '160', '175', '113', '116', '080', '086', '091', '109', '067', '110', '070', '120', '162', '064', '107', '077', '061', '076', '033', '060', '035', '108', '170', '032', '037', '092', '041', '165', '106', '068', '074', '084'}
Adding cut for subtour: {'127', '276', '005', '016', '017', '019', '009', '024', '130', '271', '015', '010', '026', '013', '129', '126', '008', '272', '022', '011', '012', '133', '277', '004', '274', '027', '006', '273', '018', '029', '020', '132', '128', '021', '023', '007', '025', '131', '014', '028', '275'}
Adding cut for subtour: {'203', '252', '209', '241', '205', '269', '141', '196', '245', '257', '225', '199', '264', '180', '134', '192', '002', '218', '190', '250', '258', '221', '247', '265', '139', '208', '202', '212', '206', '261', '237', '185', '178', '270', '176', '211', '219', '259', '246', '145', '254', '213', '244', '186', '197', '144', '179', '238', '188', '240', '140', '222', '148', '229', '235', '262', '195', '194', '135', '231', '234', '242', '001', '236', '003', '143', '255', '280', '256', '227', '137', '226', '210', '214', '187', '230', '216', '142', '268', '251', '177', '189', '232', '181', '193', '150', '182', '223', '243', '147', '201', '263', '204', '191', '228', '200', '184', '224', '267', '233', '138', '260', '239', '198', '220', '149', '207', '217', '215', '266', '249', '248', '146', '279', '278', '253', '136', '183'}
Adding cut for subtour: {'057', '044', '058', '059', '045', '056', '055', '052', '054', '050', '051', '049', '048', '046', '053', '047'}
Adding cut for subtour: {'156', '151', '152'}
Adding cut for subtour: {'154', '153', '155'}
Continue solving

Iteration 7: Finding subtours
Adding 5 cuts

Adding cut for subtour: {'089', '171', '088', '100', '039', '166', '082', '090', '114', '161', '094', '098', '078', '164', '168', '030', '125', '031', '157', '124', '121', '085', '101', '123', '063', '115', '038', '118', '093', '097', '062', '071', '172', '096', '040', '159', '105', '058', '075', '111', '117', '173', '122', '163', '112', '169', '099', '036', '073', '174', '167', '119', '069', '034', '087', '095', '102', '079', '104', '072', '042', '081', '103', '043', '158', '083', '160', '175', '113', '116', '080', '086', '091', '109', '067', '110', '070', '120', '162', '107', '077', '061', '076', '033', '060', '035', '108', '170', '032', '037', '092', '041', '165', '106', '059', '068', '074', '084'}
Adding cut for subtour: {'127', '203', '252', '005', '209', '205', '130', '269', '141', '271', '196', '257', '225', '199', '264', '180', '134', '192', '002', '218', '190', '008', '250', '258', '027', '221', '012', '247', '133', '265', '139', '277', '014', '208', '023', '025', '202', '212', '206', '261', '152', '178', '185', '270', '176', '211', '219', '259', '145', '254', '213', '129', '186', '153', '197', '144', '272', '179', '011', '004', '154', '188', '006', '222', '140', '148', '018', '151', '273', '229', '262', '195', '021', '194', '135', '001', '276', '003', '017', '143', '019', '009', '024', '255', '280', '256', '227', '137', '226', '010', '210', '013', '214', '187', '230', '126', '216', '022', '142', '268', '251', '177', '020', '189', '181', '193', '150', '182', '223', '155', '275', '016', '147', '201', '263', '204', '191', '228', '015', '200', '184', '026', '224', '267', '138', '156', '260', '198', '220', '149', '207', '274', '217', '215', '266', '029', '248', '249', '132', '128', '146', '007', '279', '278', '131', '253', '136', '028', '183'}
Adding cut for subtour: {'240', '232', '236', '243', '239', '235', '246', '241', '237', '233', '238', '231', '234', '244', '242', '245'}
Adding cut for subtour: {'057', '044', '045', '056', '055', '052', '054', '050', '051', '049', '048', '046', '053', '047'}
Adding cut for subtour: {'065', '064', '066'}
Continue solving

Iteration 8: Finding subtours
Adding 20 cuts

Adding cut for subtour: {'089', '171', '088', '100', '039', '166', '052', '082', '090', '161', '094', '098', '078', '164', '168', '030', '125', '031', '157', '124', '121', '045', '101', '123', '038', '093', '097', '057', '071', '172', '096', '047', '040', '159', '105', '058', '075', '111', '051', '173', '122', '163', '112', '169', '099', '036', '073', '174', '167', '119', '069', '034', '087', '095', '102', '079', '104', '072', '042', '081', '103', '043', '158', '083', '160', '175', '080', '091', '109', '067', '110', '070', '050', '044', '120', '046', '162', '107', '077', '061', '076', '033', '060', '054', '035', '108', '049', '170', '032', '053', '048', '037', '092', '041', '165', '106', '059', '056', '055', '068', '074', '084'}
Adding cut for subtour: {'127', '152', '178', '185', '176', '143', '147', '130', '201', '191', '196', '200', '184', '199', '180', '145', '192', '156', '187', '129', '186', '153', '190', '197', '198', '179', '142', '154', '188', '177', '020', '151', '181', '189', '193', '195', '128', '021', '194', '146', '150', '131', '182', '183', '155'}
Adding cut for subtour: {'208', '203', '252', '202', '205', '207', '253', '206', '204'}
Adding cut for subtour: {'001', '243', '005', '241', '002', '280', '242'}
Adding cut for subtour: {'209', '211', '219', '228', '227', '225', '226', '224', '210', '213', '214', '230', '244', '218', '250', '220', '216', '221', '247', '217', '251', '215', '222', '249', '248', '229', '212', '223'}
Adding cut for subtour: {'252', '263', '255', '141', '256', '259', '257', '137', '264', '267', '254', '138', '260', '258', '265', '139', '266', '148', '262', '261'}
Adding cut for subtour: {'006', '273', '276', '005', '008', '272', '007', '009', '277', '004', '274', '271', '275'}
Adding cut for subtour: {'240', '232', '236', '239', '235', '246', '237', '233', '238', '231', '234', '245'}
Adding cut for subtour: {'018', '132', '270', '016', '017', '134', '019', '133'}
Adding cut for subtour: {'026', '010', '023', '022', '027', '025', '024', '013', '012', '014', '011', '015'}
Adding cut for subtour: {'062', '115', '063', '065', '113', '116', '085', '117', '118', '114', '066', '086', '064'}
Adding cut for subtour: {'140'}
Adding cut for subtour: {'135', '136'}
Adding cut for subtour: {'003'}
Adding cut for subtour: {'126', '029', '028'}
Adding cut for subtour: {'268'}
Adding cut for subtour: {'279', '278'}
Adding cut for subtour: {'135', '269'}
Adding cut for subtour: {'144'}
Adding cut for subtour: {'149'}
Continue solving

Iteration 9: Finding subtours
Adding 11 cuts

Adding cut for subtour: {'089', '171', '088', '100', '039', '166', '052', '082', '090', '161', '094', '098', '078', '164', '168', '030', '125', '031', '157', '124', '121', '045', '101', '123', '038', '093', '097', '057', '071', '172', '096', '047', '040', '159', '105', '058', '075', '111', '051', '173', '122', '163', '112', '169', '099', '036', '073', '174', '167', '119', '069', '034', '095', '102', '079', '104', '072', '042', '081', '103', '043', '158', '083', '160', '175', '080', '091', '109', '067', '110', '070', '050', '044', '120', '046', '162', '107', '077', '061', '076', '033', '060', '054', '035', '108', '049', '170', '032', '053', '048', '037', '092', '041', '165', '106', '059', '056', '055', '068', '074'}
Adding cut for subtour: {'127', '152', '178', '185', '176', '130', '201', '191', '196', '200', '184', '199', '180', '192', '156', '187', '129', '186', '153', '190', '197', '198', '179', '154', '188', '177', '020', '151', '181', '189', '193', '195', '128', '021', '194', '150', '131', '182', '183', '155'}
Adding cut for subtour: {'208', '203', '252', '202', '205', '207', '253', '206', '204'}
Adding cut for subtour: {'001', '276', '252', '003', '005', '270', '016', '209', '017', '019', '269', '263', '255', '211', '280', '271', '256', '219', '259', '227', '257', '137', '228', '225', '226', '264', '224', '134', '267', '254', '210', '002', '213', '214', '260', '230', '244', '218', '250', '258', '220', '272', '216', '221', '133', '277', '004', '274', '268', '265', '247', '217', '251', '215', '273', '018', '266', '222', '249', '248', '132', '229', '262', '135', '223', '279', '278', '212', '136', '261', '275'}
Adding cut for subtour: {'145', '144', '146', '143', '142', '147', '141'}
Adding cut for subtour: {'240', '232', '236', '243', '239', '235', '246', '241', '237', '233', '238', '231', '234', '242', '245'}
Adding cut for subtour: {'006', '008', '026', '010', '023', '022', '027', '025', '024', '013', '012', '014', '011', '009', '007', '015'}
Adding cut for subtour: {'062', '087', '115', '063', '084', '065', '113', '116', '085', '117', '118', '114', '066', '086', '064'}
Adding cut for subtour: {'140'}
Adding cut for subtour: {'140', '148', '149', '138', '139', '141'}
Adding cut for subtour: {'126', '029', '028'}
Continue solving

Iteration 10: Finding subtours
Adding 10 cuts

Adding cut for subtour: {'089', '171', '088', '100', '039', '166', '052', '082', '090', '161', '094', '098', '078', '164', '168', '030', '125', '031', '157', '124', '121', '045', '101', '123', '038', '093', '097', '057', '071', '172', '096', '047', '040', '159', '105', '058', '075', '111', '051', '173', '122', '163', '112', '169', '099', '036', '073', '174', '167', '119', '069', '034', '087', '095', '102', '079', '104', '072', '042', '081', '103', '043', '158', '083', '160', '175', '080', '091', '109', '067', '110', '070', '050', '044', '120', '046', '162', '107', '077', '076', '033', '060', '054', '035', '108', '049', '170', '032', '053', '048', '037', '092', '041', '165', '059', '056', '055', '068', '074', '084'}
Adding cut for subtour: {'127', '203', '252', '152', '178', '185', '176', '205', '130', '201', '204', '191', '196', '200', '184', '199', '180', '145', '254', '192', '156', '187', '129', '186', '153', '190', '197', '198', '144', '179', '207', '154', '188', '177', '208', '020', '151', '181', '189', '193', '195', '128', '021', '194', '150', '253', '131', '202', '206', '182', '183', '155'}
Adding cut for subtour: {'001', '276', '003', '005', '270', '016', '017', '019', '269', '263', '255', '280', '271', '256', '259', '257', '137', '264', '134', '267', '254', '002', '260', '258', '272', '133', '277', '004', '274', '268', '265', '273', '018', '266', '132', '262', '135', '279', '278', '136', '261', '275'}
Adding cut for subtour: {'209', '211', '219', '228', '227', '225', '226', '224', '210', '213', '214', '230', '244', '218', '250', '220', '216', '221', '247', '217', '251', '215', '222', '249', '248', '229', '212', '223'}
Adding cut for subtour: {'140', '148', '146', '147', '143', '142', '149', '138', '139', '141'}
Adding cut for subtour: {'240', '232', '236', '243', '239', '235', '246', '241', '237', '233', '238', '231', '234', '242', '245'}
Adding cut for subtour: {'006', '008', '026', '010', '023', '022', '027', '025', '024', '013', '012', '014', '011', '009', '007', '015'}
Adding cut for subtour: {'061', '062', '115', '063', '065', '113', '116', '085', '117', '118', '114', '066', '086', '064'}
Adding cut for subtour: {'126', '029', '028'}
Adding cut for subtour: {'106'}
Continue solving

Iteration 11: Finding subtours
Adding 17 cuts

Adding cut for subtour: {'089', '104', '109', '110', '092', '108', '090', '103', '102', '091'}
Adding cut for subtour: {'127', '171', '100', '130', '039', '166', '052', '180', '161', '094', '098', '078', '164', '168', '030', '125', '031', '157', '124', '121', '101', '123', '038', '093', '097', '057', '071', '152', '172', '178', '185', '176', '096', '047', '040', '159', '058', '075', '051', '129', '122', '163', '186', '153', '169', '099', '179', '036', '073', '154', '188', '151', '167', '021', '069', '119', '034', '095', '072', '187', '158', '160', '175', '177', '020', '067', '181', '070', '050', '150', '182', '155', '120', '162', '077', '076', '033', '184', '054', '035', '049', '170', '032', '156', '053', '048', '037', '165', '068', '056', '055', '074', '128', '131', '183'}
Adding cut for subtour: {'208', '203', '252', '200', '199', '198', '145', '202', '205', '144', '143', '147', '207', '201', '253', '146', '206', '204'}
Adding cut for subtour: {'001', '276', '252', '003', '005', '270', '016', '209', '017', '019', '269', '263', '255', '211', '280', '271', '256', '219', '259', '227', '257', '137', '228', '225', '226', '264', '224', '134', '267', '254', '210', '002', '213', '214', '260', '230', '244', '218', '250', '258', '220', '272', '216', '221', '133', '277', '004', '274', '268', '265', '247', '217', '251', '215', '273', '018', '266', '222', '249', '248', '132', '229', '262', '135', '223', '279', '278', '212', '136', '261', '275'}
Adding cut for subtour: {'087', '112', '083', '088', '111', '084', '113', '114'}
Adding cut for subtour: {'140', '148', '149', '138', '142', '139', '141'}
Adding cut for subtour: {'240', '232', '236', '243', '239', '235', '246', '241', '237', '233', '238', '231', '234', '242', '245'}
Adding cut for subtour: {'190', '193', '197', '195', '194', '192', '191', '196'}
Adding cut for subtour: {'006', '008', '026', '010', '023', '022', '027', '025', '024', '013', '012', '014', '011', '009', '007', '015'}
Adding cut for subtour: {'061', '062', '115', '063', '065', '116', '085', '117', '118', '066', '086', '064'}
Adding cut for subtour: {'045', '046'}
Adding cut for subtour: {'106', '105', '107', '173', '174'}
Adding cut for subtour: {'126', '029', '028'}
Adding cut for subtour: {'079', '082', '081', '080'}
Adding cut for subtour: {'041', '043', '044', '042'}
Adding cut for subtour: {'045', '044', '059', '060'}
Adding cut for subtour: {'189'}
Continue solving

Iteration 12: Finding subtours
Adding 5 cuts

Adding cut for subtour: {'089', '171', '088', '100', '039', '166', '052', '082', '090', '114', '161', '094', '065', '098', '078', '164', '168', '030', '125', '031', '157', '124', '121', '085', '066', '045', '101', '123', '063', '115', '038', '118', '093', '097', '062', '057', '071', '172', '096', '047', '040', '159', '105', '058', '075', '051', '117', '173', '122', '163', '112', '169', '099', '036', '073', '174', '167', '119', '069', '034', '087', '095', '102', '079', '104', '072', '042', '081', '103', '043', '158', '083', '160', '175', '113', '116', '080', '086', '091', '067', '070', '050', '044', '120', '046', '162', '064', '107', '077', '061', '076', '033', '060', '054', '035', '049', '170', '032', '053', '048', '037', '092', '041', '165', '106', '059', '056', '055', '068', '074', '084'}
Adding cut for subtour: {'127', '203', '252', '005', '209', '241', '205', '130', '269', '271', '196', '245', '257', '225', '264', '180', '134', '192', '002', '218', '190', '008', '250', '258', '027', '221', '012', '247', '133', '265', '277', '014', '208', '023', '025', '202', '212', '206', '261', '237', '152', '178', '185', '270', '176', '211', '219', '259', '246', '254', '213', '129', '244', '186', '153', '197', '272', '179', '011', '238', '004', '154', '188', '240', '006', '222', '018', '273', '151', '229', '235', '262', '195', '021', '194', '135', '231', '234', '242', '001', '276', '236', '003', '017', '019', '009', '024', '255', '280', '256', '227', '137', '226', '010', '210', '013', '214', '187', '230', '126', '216', '022', '268', '251', '177', '020', '189', '181', '232', '193', '150', '182', '223', '155', '275', '243', '016', '201', '263', '204', '191', '228', '015', '184', '026', '224', '267', '233', '156', '260', '239', '198', '220', '207', '274', '217', '215', '266', '029', '248', '249', '132', '128', '007', '279', '278', '131', '253', '136', '028', '183'}
Adding cut for subtour: {'140', '148', '200', '199', '145', '144', '147', '143', '142', '146', '149', '138', '139', '141'}
Adding cut for subtour: {'111'}
Adding cut for subtour: {'110', '109', '108'}
Continue solving

Iteration 13: Finding subtours
Adding 3 cuts

Adding cut for subtour: {'089', '171', '088', '100', '039', '166', '052', '082', '090', '114', '161', '094', '065', '098', '078', '164', '168', '030', '125', '031', '157', '124', '121', '085', '066', '045', '101', '123', '063', '115', '038', '118', '093', '097', '062', '057', '071', '172', '096', '047', '040', '159', '105', '058', '075', '111', '051', '117', '173', '122', '163', '112', '169', '099', '036', '073', '174', '167', '119', '069', '034', '087', '095', '102', '079', '104', '072', '042', '081', '103', '043', '158', '083', '160', '175', '113', '116', '080', '086', '091', '109', '067', '110', '070', '050', '044', '120', '046', '162', '064', '107', '077', '061', '076', '033', '060', '054', '035', '108', '049', '170', '032', '053', '048', '037', '092', '041', '165', '059', '056', '055', '068', '074', '084'}
Adding cut for subtour: {'127', '203', '252', '005', '209', '241', '205', '130', '269', '141', '271', '196', '245', '257', '225', '199', '264', '180', '134', '192', '002', '218', '190', '008', '250', '258', '027', '221', '012', '247', '133', '265', '139', '277', '014', '208', '023', '025', '202', '212', '206', '261', '237', '152', '178', '185', '270', '176', '211', '219', '259', '246', '145', '254', '213', '129', '244', '186', '153', '197', '144', '272', '179', '011', '238', '004', '154', '188', '240', '006', '140', '222', '148', '018', '151', '273', '229', '235', '262', '195', '021', '194', '135', '231', '234', '242', '001', '276', '236', '003', '017', '143', '019', '009', '024', '255', '280', '256', '227', '137', '226', '010', '210', '013', '214', '187', '230', '126', '216', '022', '142', '268', '251', '177', '020', '189', '181', '232', '193', '150', '182', '223', '155', '275', '243', '016', '147', '201', '263', '204', '191', '228', '015', '200', '184', '026', '224', '267', '233', '138', '156', '260', '239', '198', '220', '149', '207', '274', '217', '215', '266', '029', '248', '249', '132', '128', '146', '007', '279', '278', '131', '253', '136', '028', '183'}
Adding cut for subtour: {'106'}
Continue solving

Iteration 14: Finding subtours
Adding 8 cuts

Adding cut for subtour: {'089', '171', '127', '100', '130', '196', '199', '166', '180', '090', '192', '161', '094', '098', '164', '168', '125', '157', '190', '124', '121', '101', '123', '093', '097', '152', '172', '178', '185', '176', '096', '159', '105', '173', '122', '129', '163', '186', '153', '169', '099', '197', '179', '154', '188', '174', '151', '167', '195', '021', '194', '119', '095', '102', '104', '103', '187', '158', '126', '160', '175', '091', '177', '020', '189', '181', '193', '150', '182', '155', '120', '201', '162', '107', '191', '200', '184', '108', '170', '156', '092', '198', '165', '106', '128', '131', '183'}
Adding cut for subtour: {'208', '203', '252', '202', '205', '207', '253', '206', '204'}
Adding cut for subtour: {'005', '209', '241', '269', '271', '245', '257', '225', '264', '134', '002', '218', '250', '258', '221', '133', '277', '265', '247', '212', '261', '237', '270', '211', '219', '259', '246', '254', '213', '244', '272', '238', '004', '240', '273', '018', '222', '229', '235', '262', '135', '231', '234', '242', '001', '276', '236', '003', '017', '019', '255', '280', '256', '227', '137', '226', '210', '214', '230', '216', '268', '251', '232', '223', '275', '243', '016', '263', '228', '224', '267', '233', '260', '239', '220', '274', '217', '215', '266', '249', '248', '132', '279', '278', '136'}
Adding cut for subtour: {'057', '087', '071', '044', '088', '009', '024', '046', '079', '047', '077', '040', '015', '072', '039', '042', '076', '081', '058', '075', '054', '052', '060', '082', '051', '035', '049', '026', '010', '013', '032', '053', '048', '078', '043', '037', '033', '030', '031', '083', '008', '022', '027', '011', '036', '012', '073', '080', '041', '006', '029', '045', '067', '059', '068', '056', '055', '070', '074', '084', '050', '023', '007', '025', '038', '069', '014', '028', '034'}
Adding cut for subtour: {'140', '148', '145', '144', '147', '143', '142', '146', '149', '138', '139', '141'}
Adding cut for subtour: {'109', '110', '113', '116', '085', '086'}
Adding cut for subtour: {'062', '061', '114', '112', '115', '063', '111', '117', '118', '066', '064'}
Adding cut for subtour: {'065'}
Continue solving

Iteration 15: Finding subtours
Adding 26 cuts

Adding cut for subtour: {'089', '171', '152', '172', '185', '100', '178', '095', '120', '176', '096', '102', '191', '107', '159', '104', '105', '184', '166', '180', '108', '090', '192', '103', '170', '173', '156', '187', '094', '129', '098', '122', '161', '158', '168', '186', '126', '153', '125', '157', '169', '190', '099', '124', '160', '175', '092', '179', '121', '154', '091', '188', '174', '177', '165', '183', '106', '189', '151', '181', '101', '167', '193', '123', '110', '109', '128', '150', '119', '093', '182', '097', '155'}
Adding cut for subtour: {'127'}
Adding cut for subtour: {'203', '252', '270', '209', '205', '147', '143', '269', '201', '263', '141', '255', '211', '204', '256', '219', '259', '227', '257', '137', '228', '225', '200', '199', '226', '264', '224', '145', '134', '267', '254', '138', '210', '213', '214', '260', '230', '244', '218', '250', '198', '258', '144', '149', '216', '142', '220', '207', '221', '265', '139', '268', '247', '217', '251', '215', '208', '140', '266', '148', '222', '249', '248', '229', '262', '146', '135', '253', '202', '212', '136', '206', '261', '223'}
Adding cut for subtour: {'001', '243', '005', '241', '002', '280', '242'}
Adding cut for subtour: {'057', '087', '071', '044', '088', '079', '077', '040', '072', '039', '042', '076', '081', '058', '075', '060', '082', '035', '043', '078', '037', '083', '036', '073', '080', '041', '059', '067', '068', '070', '074', '084', '038', '069', '034'}
Adding cut for subtour: {'018', '132', '017', '019', '130', '131', '133'}
Adding cut for subtour: {'006', '273', '276', '005', '008', '272', '007', '009', '277', '004', '274', '271', '275'}
Adding cut for subtour: {'240', '232', '236', '239', '235', '246', '237', '233', '238', '231', '234', '245'}
Adding cut for subtour: {'045', '054', '055', '052', '046', '053'}
Adding cut for subtour: {'030', '031', '033', '032'}
Adding cut for subtour: {'026', '010', '023', '022', '027', '025', '024', '013', '012', '014', '011', '015'}
Adding cut for subtour: {'065', '085', '066'}
Adding cut for subtour: {'062', '063', '064'}
Adding cut for subtour: {'061', '115', '111', '117', '118', '114'}
Adding cut for subtour: {'112'}
Adding cut for subtour: {'194', '197', '195', '196'}
Adding cut for subtour: {'003'}
Adding cut for subtour: {'086', '113', '116'}
Adding cut for subtour: {'130', '020', '021'}
Adding cut for subtour: {'048', '047', '050', '049'}
Adding cut for subtour: {'162', '164', '163'}
Adding cut for subtour: {'056'}
Adding cut for subtour: {'279', '278'}
Adding cut for subtour: {'028', '029'}
Adding cut for subtour: {'051'}
Adding cut for subtour: {'016'}
Continue solving

Iteration 16: Finding subtours
Adding 5 cuts

Adding cut for subtour: {'089', '171', '127', '203', '252', '005', '088', '100', '209', '241', '205', '269', '141', '271', '196', '245', '257', '039', '225', '199', '166', '264', '180', '082', '134', '090', '192', '161', '094', '098', '078', '164', '168', '030', '125', '218', '031', '157', '190', '008', '124', '250', '258', '121', '221', '012', '247', '133', '265', '139', '277', '014', '027', '208', '045', '101', '123', '023', '025', '038', '202', '212', '093', '206', '261', '097', '237', '057', '071', '152', '172', '178', '185', '270', '176', '096', '211', '219', '040', '259', '159', '058', '105', '075', '246', '145', '254', '213', '173', '122', '129', '244', '163', '186', '153', '169', '099', '197', '144', '272', '179', '011', '036', '238', '004', '073', '154', '188', '240', '174', '006', '140', '222', '148', '018', '151', '273', '167', '229', '235', '262', '195', '194', '135', '119', '069', '231', '234', '034', '242', '001', '276', '087', '236', '003', '095', '017', '143', '019', '009', '024', '102', '255', '280', '079', '256', '227', '072', '137', '104', '042', '081', '226', '010', '210', '013', '103', '214', '187', '230', '043', '158', '126', '083', '160', '175', '216', '022', '142', '080', '268', '091', '251', '177', '109', '189', '232', '181', '067', '193', '110', '070', '150', '182', '223', '155', '275', '044', '243', '016', '120', '147', '201', '046', '263', '162', '204', '191', '228', '015', '077', '107', '076', '200', '184', '033', '060', '026', '224', '035', '108', '267', '233', '138', '170', '032', '156', '260', '037', '239', '092', '198', '220', '149', '207', '274', '041', '217', '165', '215', '266', '029', '106', '248', '249', '059', '132', '055', '056', '068', '074', '128', '084', '146', '007', '279', '278', '253', '136', '028', '183'}
Adding cut for subtour: {'020', '130', '131', '021'}
Adding cut for subtour: {'054', '052', '050', '051', '049', '048', '053', '047'}
Adding cut for subtour: {'061', '062', '112', '115', '063', '111', '065', '113', '116', '085', '117', '118', '114', '066', '086', '064'}
Adding cut for subtour: {'002'}
Continue solving

Iteration 17: Finding subtours
Adding 2 cuts

Adding cut for subtour: {'089', '171', '127', '203', '252', '005', '088', '100', '209', '241', '205', '269', '130', '141', '271', '196', '245', '257', '039', '225', '199', '166', '052', '264', '180', '082', '134', '090', '192', '114', '161', '094', '065', '098', '078', '164', '168', '030', '125', '218', '031', '157', '190', '008', '124', '250', '258', '121', '221', '012', '247', '133', '265', '139', '277', '014', '027', '066', '208', '045', '101', '123', '115', '063', '023', '025', '038', '118', '202', '212', '093', '206', '261', '097', '237', '062', '057', '071', '152', '172', '178', '185', '270', '176', '096', '211', '219', '047', '040', '259', '159', '105', '058', '075', '246', '051', '145', '111', '254', '213', '117', '173', '122', '129', '244', '163', '186', '153', '112', '169', '099', '197', '144', '272', '179', '011', '036', '238', '004', '073', '154', '188', '240', '174', '006', '140', '222', '148', '018', '151', '273', '085', '167', '229', '235', '262', '195', '021', '194', '135', '119', '069', '231', '234', '034', '242', '001', '276', '087', '236', '003', '095', '017', '143', '019', '009', '024', '102', '255', '280', '079', '256', '227', '104', '137', '072', '042', '081', '226', '010', '210', '103', '013', '214', '187', '230', '043', '158', '126', '083', '160', '175', '216', '022', '142', '116', '113', '080', '268', '091', '086', '251', '177', '109', '189', '232', '181', '020', '193', '067', '110', '070', '050', '150', '182', '223', '155', '275', '044', '243', '016', '120', '147', '201', '046', '263', '162', '064', '204', '107', '191', '228', '015', '077', '061', '076', '200', '184', '033', '060', '026', '054', '224', '035', '108', '049', '267', '233', '138', '170', '032', '156', '260', '053', '048', '037', '239', '092', '198', '220', '149', '207', '274', '041', '217', '165', '215', '266', '029', '106', '248', '249', '059', '132', '055', '056', '068', '074', '128', '084', '146', '007', '279', '278', '131', '253', '136', '028', '183'}

Iteration 18: Finding subtours
Adding 4 cuts

Adding cut for subtour: {'089', '171', '127', '203', '252', '005', '088', '100', '209', '241', '205', '130', '269', '141', '271', '245', '196', '257', '039', '225', '199', '166', '264', '180', '082', '134', '090', '192', '002', '114', '161', '065', '098', '078', '164', '168', '030', '125', '218', '031', '157', '190', '008', '124', '250', '258', '121', '027', '012', '133', '277', '265', '247', '221', '139', '066', '085', '208', '045', '101', '123', '063', '115', '023', '025', '038', '118', '202', '212', '093', '206', '261', '062', '057', '071', '152', '172', '270', '185', '178', '176', '211', '219', '040', '259', '159', '105', '058', '075', '111', '145', '254', '213', '117', '173', '122', '129', '244', '163', '186', '153', '112', '169', '099', '197', '144', '272', '179', '011', '036', '073', '004', '154', '188', '240', '174', '006', '273', '018', '222', '148', '140', '151', '167', '229', '262', '195', '021', '194', '135', '119', '069', '034', '242', '001', '276', '087', '003', '017', '019', '009', '024', '143', '102', '255', '280', '079', '256', '227', '104', '137', '072', '042', '081', '226', '010', '210', '103', '013', '214', '187', '230', '043', '158', '126', '083', '160', '175', '022', '216', '142', '113', '116', '080', '268', '091', '086', '251', '177', '109', '020', '189', '181', '067', '193', '110', '070', '150', '182', '275', '223', '155', '044', '243', '016', '120', '147', '201', '263', '162', '064', '204', '107', '015', '228', '191', '061', '077', '076', '200', '184', '033', '060', '026', '224', '035', '108', '267', '138', '170', '032', '156', '260', '037', '092', '198', '220', '149', '207', '274', '041', '217', '165', '215', '266', '029', '106', '249', '248', '059', '132', '056', '068', '074', '128', '084', '146', '007', '253', '279', '278', '131', '014', '136', '028', '183'}
Adding cut for subtour: {'054', '055', '052', '050', '051', '049', '048', '046', '053', '047'}
Adding cut for subtour: {'094', '095', '097', '096'}
Adding cut for subtour: {'232', '236', '239', '235', '246', '233', '238', '231', '234', '237'}
Continue solving

Iteration 19: Finding subtours
Adding 3 cuts

Adding cut for subtour: {'089', '171', '127', '005', '088', '100', '269', '271', '196', '039', '199', '166', '052', '082', '180', '134', '090', '192', '002', '114', '161', '094', '065', '098', '078', '164', '168', '030', '125', '031', '157', '190', '008', '124', '121', '027', '012', '085', '277', '066', '139', '045', '101', '123', '115', '063', '023', '025', '038', '118', '093', '097', '062', '057', '071', '152', '172', '178', '185', '270', '176', '096', '047', '040', '159', '105', '058', '075', '111', '051', '145', '117', '173', '122', '129', '163', '186', '153', '112', '169', '099', '197', '272', '179', '011', '036', '073', '004', '154', '188', '174', '006', '273', '148', '151', '167', '195', '194', '135', '119', '069', '034', '001', '276', '087', '003', '095', '009', '024', '102', '280', '079', '104', '137', '072', '042', '081', '010', '103', '013', '187', '043', '158', '126', '083', '160', '175', '022', '113', '116', '080', '268', '091', '086', '177', '109', '189', '067', '181', '193', '110', '070', '050', '150', '182', '275', '155', '044', '016', '120', '046', '162', '064', '107', '191', '015', '077', '061', '076', '033', '184', '060', '054', '026', '035', '108', '049', '267', '138', '170', '032', '156', '053', '048', '037', '092', '198', '149', '274', '041', '165', '029', '106', '059', '056', '055', '068', '074', '128', '084', '146', '007', '279', '278', '014', '136', '028', '183'}
Adding cut for subtour: {'203', '243', '252', '236', '209', '241', '205', '143', '147', '201', '263', '141', '255', '219', '204', '256', '228', '259', '245', '257', '227', '234', '225', '200', '226', '264', '246', '224', '254', '233', '210', '213', '214', '260', '230', '244', '218', '239', '231', '250', '258', '144', '220', '216', '142', '221', '207', '238', '265', '247', '240', '217', '251', '215', '208', '140', '266', '222', '249', '248', '232', '229', '235', '262', '211', '223', '253', '202', '212', '206', '261', '242', '237'}
Adding cut for subtour: {'018', '020', '132', '017', '021', '019', '133', '130', '131'}
Continue solving

Iteration 20: Finding subtours
Adding 3 cuts

Adding cut for subtour: {'089', '171', '127', '203', '252', '005', '088', '100', '209', '241', '205', '130', '269', '141', '271', '196', '245', '257', '039', '225', '199', '166', '264', '180', '082', '134', '090', '192', '002', '114', '161', '094', '065', '098', '078', '164', '168', '030', '125', '218', '031', '157', '190', '008', '124', '250', '258', '121', '221', '012', '247', '133', '265', '139', '277', '014', '027', '066', '208', '101', '123', '063', '115', '023', '025', '038', '118', '202', '212', '093', '206', '261', '097', '237', '062', '057', '071', '152', '172', '178', '185', '270', '176', '096', '211', '219', '040', '259', '159', '105', '058', '075', '246', '111', '254', '213', '117', '173', '122', '129', '244', '163', '186', '153', '112', '169', '099', '197', '272', '179', '011', '036', '238', '004', '073', '154', '188', '240', '174', '006', '222', '140', '148', '018', '151', '273', '085', '167', '229', '235', '262', '195', '021', '194', '135', '119', '069', '231', '234', '034', '242', '001', '276', '087', '236', '003', '095', '017', '019', '009', '024', '102', '255', '280', '079', '256', '227', '104', '137', '072', '042', '081', '226', '010', '210', '103', '013', '214', '187', '230', '043', '158', '126', '083', '160', '175', '216', '022', '142', '113', '116', '080', '268', '091', '086', '251', '177', '109', '020', '189', '181', '232', '193', '067', '110', '070', '150', '182', '223', '155', '275', '044', '243', '016', '120', '147', '201', '263', '162', '064', '204', '107', '191', '228', '015', '061', '077', '076', '200', '184', '033', '060', '026', '224', '035', '108', '267', '233', '138', '170', '032', '156', '260', '037', '239', '092', '198', '220', '149', '207', '274', '041', '217', '165', '215', '266', '029', '106', '248', '249', '059', '132', '068', '074', '128', '084', '007', '279', '278', '131', '253', '136', '028', '183'}
Adding cut for subtour: {'045', '056', '055', '052', '054', '050', '051', '049', '048', '046', '053', '047'}
Adding cut for subtour: {'144', '143', '146', '145'}
Continue solving

Iteration 21: Finding subtours
No subtours detected. Not adding any cut

Iteration 22: Finding subtours
Adding 2 cuts

Adding cut for subtour: {'089', '171', '127', '203', '005', '088', '100', '209', '241', '205', '130', '269', '141', '271', '196', '245', '257', '039', '225', '199', '166', '052', '264', '180', '082', '134', '090', '192', '002', '114', '161', '094', '065', '098', '078', '164', '168', '030', '125', '218', '031', '157', '190', '008', '124', '250', '258', '121', '221', '012', '247', '133', '265', '139', '277', '027', '066', '085', '208', '045', '101', '123', '063', '115', '023', '025', '038', '118', '202', '212', '093', '206', '261', '097', '237', '062', '057', '071', '152', '172', '178', '185', '270', '176', '096', '211', '219', '047', '040', '259', '159', '105', '058', '075', '246', '051', '145', '111', '213', '117', '173', '122', '129', '244', '163', '186', '153', '112', '169', '099', '197', '144', '272', '179', '011', '036', '238', '004', '073', '154', '188', '240', '174', '006', '140', '222', '148', '018', '151', '273', '167', '229', '235', '262', '195', '021', '194', '135', '119', '069', '231', '234', '034', '242', '001', '276', '087', '236', '003', '095', '017', '143', '019', '009', '024', '102', '280', '079', '256', '227', '104', '137', '072', '042', '081', '226', '010', '210', '103', '013', '214', '187', '230', '043', '158', '126', '083', '160', '175', '216', '022', '142', '116', '113', '080', '268', '091', '086', '251', '177', '109', '189', '232', '181', '020', '193', '067', '110', '070', '050', '150', '182', '223', '155', '275', '044', '243', '016', '120', '147', '201', '046', '263', '162', '064', '204', '107', '191', '228', '015', '061', '077', '076', '200', '184', '033', '060', '026', '054', '224', '035', '108', '049', '267', '233', '138', '170', '032', '156', '260', '053', '048', '037', '239', '092', '198', '220', '149', '207', '274', '041', '217', '165', '215', '266', '029', '106', '248', '249', '059', '132', '055', '056', '068', '074', '128', '084', '146', '007', '279', '278', '131', '014', '136', '028', '183'}

Iteration 23: Finding subtours
No subtours detected. Not adding any cut

Iteration 24: Finding subtours
Adding 2 cuts

Adding cut for subtour: {'089', '171', '127', '005', '088', '100', '271', '039', '166', '052', '082', '090', '002', '114', '161', '094', '065', '098', '078', '164', '168', '030', '125', '031', '157', '008', '124', '121', '027', '012', '085', '277', '066', '045', '101', '123', '115', '063', '023', '025', '038', '118', '093', '097', '062', '057', '071', '172', '096', '047', '040', '159', '105', '058', '075', '111', '051', '117', '173', '122', '163', '112', '169', '099', '272', '011', '036', '073', '004', '174', '006', '273', '018', '167', '021', '119', '069', '034', '001', '276', '087', '003', '095', '017', '019', '009', '024', '102', '280', '079', '104', '072', '042', '081', '010', '103', '013', '043', '158', '126', '083', '160', '175', '022', '113', '116', '080', '086', '091', '109', '020', '067', '110', '070', '050', '275', '044', '016', '120', '046', '162', '064', '107', '015', '077', '061', '076', '033', '060', '054', '026', '035', '108', '049', '170', '032', '053', '048', '037', '092', '274', '041', '165', '029', '106', '059', '056', '055', '068', '074', '128', '084', '007', '279', '278', '014', '028'}

Iteration 25: Finding subtours
Adding 2 cuts

Adding cut for subtour: {'089', '171', '127', '203', '005', '088', '100', '241', '205', '130', '269', '141', '271', '196', '245', '257', '039', '225', '199', '166', '052', '264', '180', '082', '134', '090', '192', '002', '114', '161', '094', '065', '098', '078', '164', '168', '030', '125', '218', '031', '157', '190', '008', '124', '250', '258', '121', '221', '012', '247', '133', '265', '139', '277', '027', '066', '085', '045', '101', '123', '063', '115', '023', '025', '038', '118', '202', '212', '093', '206', '261', '097', '237', '062', '057', '071', '152', '172', '178', '185', '270', '176', '096', '211', '219', '047', '040', '259', '159', '105', '058', '075', '246', '051', '145', '111', '213', '117', '173', '122', '129', '244', '163', '186', '153', '112', '169', '099', '197', '144', '272', '179', '011', '036', '238', '004', '073', '154', '188', '240', '174', '006', '222', '140', '148', '018', '151', '273', '167', '229', '235', '262', '195', '021', '194', '135', '119', '069', '231', '234', '034', '242', '001', '276', '087', '236', '003', '095', '017', '143', '019', '009', '024', '102', '280', '079', '256', '227', '104', '137', '072', '042', '081', '226', '010', '210', '103', '013', '214', '187', '230', '043', '158', '126', '083', '160', '175', '216', '022', '142', '113', '116', '080', '268', '091', '086', '251', '177', '109', '020', '189', '181', '232', '193', '067', '110', '070', '050', '150', '182', '223', '155', '275', '044', '243', '016', '120', '147', '201', '046', '263', '162', '064', '204', '107', '191', '228', '015', '061', '077', '076', '200', '184', '033', '060', '026', '054', '224', '035', '108', '049', '267', '233', '138', '170', '032', '156', '260', '053', '048', '037', '239', '092', '198', '220', '149', '207', '274', '041', '217', '165', '215', '266', '029', '106', '248', '249', '059', '132', '055', '056', '068', '074', '128', '084', '146', '007', '279', '278', '131', '014', '136', '028', '183'}

Iteration 26: Finding subtours
No subtours detected. Not adding any cut
Gurobi 10.0.2: optimal solution; objective 2586.76964756316
3196 simplex iterations
516 branching nodes
absmipgap=9.09495e-13, relmipgap=0

Get the solution, print it and display it

# Get the solution into ARCS
ARCS = ampl.get_data("{(i,j) in PAIRS : X[i,j] > 0} X[i,j];")
ARCS = set([(i, j) for (i, j, k) in ARCS.toList()])

# Display it
tours = findSubTours(ARCS, NODES)
for st in tours:
    print(st)
plotTours(tours, CPOINTS)

['089', '090', '091', '092', '093', '094', '095', '096', '097', '098', '099', '100', '101', '102', '103', '104', '105', '106', '107', '174', '173', '172', '171', '170', '169', '168', '167', '166', '165', '164', '163', '162', '161', '175', '160', '159', '158', '157', '119', '120', '121', '122', '123', '124', '125', '030', '126', '127', '128', '021', '020', '019', '132', '131', '130', '129', '154', '155', '153', '156', '152', '151', '177', '178', '150', '179', '180', '176', '181', '182', '183', '184', '185', '186', '187', '188', '189', '190', '191', '192', '193', '197', '194', '195', '196', '201', '198', '199', '200', '202', '203', '204', '205', '206', '207', '208', '209', '210', '211', '212', '213', '214', '215', '216', '217', '218', '219', '220', '221', '222', '223', '224', '225', '226', '227', '228', '229', '230', '251', '250', '247', '245', '246', '231', '232', '233', '234', '235', '236', '237', '238', '239', '240', '241', '244', '243', '242', '002', '001', '280', '003', '279', '278', '248', '249', '256', '255', '252', '253', '254', '257', '258', '259', '260', '261', '262', '263', '264', '265', '266', '140', '141', '142', '143', '144', '145', '146', '147', '148', '149', '139', '138', '137', '267', '268', '136', '135', '269', '270', '134', '133', '018', '017', '016', '271', '272', '273', '274', '275', '276', '277', '004', '005', '006', '007', '008', '009', '010', '011', '012', '013', '015', '014', '024', '023', '025', '022', '026', '027', '028', '029', '031', '032', '033', '034', '035', '036', '037', '038', '039', '040', '041', '042', '043', '060', '061', '118', '062', '063', '059', '044', '045', '046', '047', '048', '049', '050', '051', '052', '053', '054', '055', '056', '057', '058', '064', '065', '066', '067', '068', '069', '070', '071', '072', '073', '074', '075', '076', '077', '078', '079', '080', '081', '082', '083', '084', '085', '086', '116', '117', '115', '114', '113', '087', '088', '112', '111', '110', '108', '109']

ampl.get_value("Tour_Length")

2586.769647563161

time() - t0  # seconds

25.828405618667603

previous

Transportation problem

next

Unit Commitment for Electrical Power Generation