Package tsp
Top-level package for tsp.
Expand source code
# -*- coding: utf-8 -*-
"""Top-level package for tsp."""
__author__ = """Andreas Klose"""
__email__ = 'aklose@math.au.dk'
__version__ = '3.0'
__date__ = '14/04/2023'
from . import tsp_plot
from . import tsp_heu
from . import tsp_match
from . import tsp_trees
from . import tsp_hk
from . import tsp_cpx
from . import concorde
from .tsp_heu import nearestNeighbour
from .tsp_heu import doInsertion
from .tsp_heu import minSpanTree
from .tsp_heu import christofides
from .tsp_plot import displayPoints
from .tsp_plot import displayRoute
from .tsp_plot import plotEdgeList
from .tsp_plot import set_tk_window
from .tsp_match import assignLB
from .tsp_match import twoMatch
from .tsp_trees import oneTree
from .tsp_trees import fast1Tree
from .tsp_hk import LR_1tree
from .concorde import solveTSP
from .tsp_cpx import CPXtspSolve
from itertools import combinations as combinat
import matplotlib.pyplot as plt
import tsplib95 as tl
import platform
#-----------------------------------------------------------------------
def default_wait():
"""
Default wait function used for waiting on user input/action to
proceed with computations after plotting if Matplot.pyplot runs
in interactive mode. The action is to click into the drawing window.
"""
plt.waitforbuttonpress(timeout=-1)
#-----------------------------------------------------------------------
class TSP:
def __init__(self, fname=None, problem = None, interactive=True,
anim_route=False, no_wait=False, fontsize=6 ):
"""
Initialize instance of class TSP.
Parameters:
**fname** : str, optional
None or the name of the input data file readable by module
tsplib95. If fname is not None, the problem data is
read from file fname using tsplib95.load(). Note that
then "problem" is ignored even if it is not None.
**problem** : class, optional
None or a tsp problem instance (cf. module tsplib95).
**interactive** : bool, optional
If True and Matplotlib.pyplot is in non-interactive mode,
pyplot is put into interactive mode. This then usually
requires that after plotting something, a function
is called to wait for user input/action. This is in
this case, a click inside the window as long as the
option no_wait is not True, otherwise there is no
waiting after plotting.
Default=True.
**anim_route** : bool, optional
If True, Hamiltonian cycles are drawn in animated way, slowly
edge by edge, if the solution is drawn/displayed. Otherwise,
the cycle is just drawn if displayed.
**fontsize** : int, optional
Size of font in drawings. Default = 6.
"""
self.anim_route = anim_route
""" Draw route in animated way or not"""
self.fontsize = fontsize
"""Fontsize used in drawings"""
self.one = 0.99999
"""Approximation for 1"""
self.problem = None
"""The problem instance (cf. tsplib95 for documentation)"""
self.route = None
"""The sequence nodes are visited in current solution."""
self.routeLen = 0
"""The length of the current route"""
self.broute = None
"""Sequence of nodes as visited in best solution so far"""
self.brouteLen = 0
"""Length of best route found so far"""
self.sol_method = ""
"""Name of the solution method that created the solution"""
self.lobnd = None
"""A lower bound on the shortest route"""
self.elist = None
"""A list of edges, e.g., in a minimum weight 1-tree"""
self.xvals = None
"""Solution values to edge variables"""
self.errMsg = ""
self.logFile = 'nul' if 'Windows' in platform.system() else '/dev/null'
self.wait = None
if interactive and not plt.isinteractive():
if not no_wait: self.wait = default_wait
plt.ion()
if not fname is None:
try:
p = tl.load(fname)
self.problem = p
except:
self.problem = None
self.errMsg = "Unable to read data from file "+fname
else:
self.problem = problem
p = self.problem
if p is not None:
# Set the weight function
try:
_ = p.wfunc # tsplib95 version before 0.7.1
except:
self.problem.wfunc = p._wfunc # tsplib95, version 0.7.1
# Check if symmetric TSP
if not p.is_symmetric():
if p.is_special() or self.really_asymmetric():
self.errMsg = "Cannot treat the asymmetric TSP."
self.problem = None
else:
# Distance matrix is full matrix type. Change to lower row,
# as otherwise stupid tsplib95 thinks it is asymmetric
p.edge_weight_format = 'LOWER_ROW'
if interactive and not plt.isinteractive(): plt.ion()
if not interactive and plt.isinteractive(): plt.ioff()
def really_asymmetric(self):
"""
Checks if distances in the TSP problem are asymmetric
"""
p = self.problem
return max(abs(p.get_weight(e[0],e[1])-p.get_weight(e[1],e[0])) \
for e in combinat(p.get_nodes(),2)) > 0
def get_length(self, route):
"""
Compute length of route "route"
"""
if route is None or self.problem is None: return 0
p = self.problem
L = sum(p.wfunc(route[i-1],route[i]) for i in range(1,p.dimension))
if route[0] != route[-1]: L += p.wfunc(route[-1],route[0])
return L
def displayPoints(self):
"""
Plot the nodes/points appearing in the problem instance
"""
if self.problem.is_depictable():
displayPoints(self.problem, wait_func=self.wait)
def showSol(self):
"""
Plot the route.
"""
if self.problem.is_depictable():
displayRoute(self.problem,self.route,self.routeLen,animate=self.anim_route,\
wait_func=self.wait, fontsize=self.fontsize,\
title=self.sol_method)
else:
print("Solution obtained by",self.sol_method)
print(" Route length:",self.routeLen)
print(" Route :",self.route)
def showBestSol(self):
"""
Plot the best route found so far
"""
if self.problem.is_depictable():
displayRoute(self.problem,self.broute,self.brouteLen,animate=self.anim_route,\
wait_func=self.wait, fontsize=self.fontsize,\
title="Best solution found so far")
else:
print("Best solution found so far:")
print(" Route length:",self.routeLen)
print(" Route :",self.route)
def showEdgeList( self ):
"""
Plot the edges selected in a relaxation that was solved to
obtain a lower bound on the shortest route.
Parameters:
**xvals** : None or list of float
If not None the (fractional) values of the edge
variables in the solution to the relaxation.
"""
if self.problem.is_depictable():
info = self.sol_method + ". Lower bound: "+str(self.lobnd)
elst = self.elist
efract = None
if not self.xvals is None:
efract = [elst[i] for i in range(len(elst)) if self.xvals[i] < self.one]
plotEdgeList( self.problem, elst, specialEdges=efract, title = info,\
fontsize=self.fontsize, wait_func=self.wait )
else:
print("Lower bound :",self.lobnd)
print("Edges selected:",self.elist)
def solve( self, method, anim=False, wait_func=None, nodeLim=None, log_output=True ):
"""
Solve the problem instance using method "method!. The solution
is stored in a list self.route that gives the sequence in which
the nodes are visited and in a float (or int) called routeLen,
the length of the route.
Parameters:
**method** : str
Indicates the solution method to be applied and must
be one of the following:
- NN for nearest neighbour heuristic
- NI for nearest insertion
- FI for farthest insertion
- MST for min. spanning tree heuristic
- CHRISTO for Christofides' heuristic
- LK for Concorde's Lin-Kernighan heuristic
- CC for Concorde's exact branch-and-cut method
- CPX for Cplex MIP solver
- 2CFF for Cplex applied on the 2-commodity flow formulation
- 2CFFSCE for 2-commodity flow + subcyle elimination cuts
**anim** : bool
If True, the solution method is run with animation active
(as far as it has animation).
**nodeLim** : int
Limits the number of nodes that Cplex is going to enumerate
If anim=True, it is strongly recommended to set the NodeLim
to 1 so that just at the root node animated graphics are
shown.
**log_output** : bool
If True, the default, and Cplex is used to solve the problem,
Cplex sends messages on the solution progress to the screen.
Remark:
The methods that use Cplex (CPX, 2CFF, 2CFFSCE) makes use of the
attributes "route" to set an initial start solution, provided
of course route is not None.
"""
if anim and not self.problem.is_depictable(): anim=False
method.replace(" ","")
method = method.upper()
logFile = None if log_output else self.logFile
if anim and plt.isinteractive() and wait_func is None:
wait_func = self.wait
s, r, L = None, None, None
if method == 'NN':
s = 'Nearest neighbour route '
L, r = nearestNeighbour( self.problem )
elif method == 'NI':
s = 'Nearest insertion route '
L, r = doInsertion( self.problem )
elif method == 'FI':
s = 'Farthest insertion route '
L, r = doInsertion( self.problem, nearest=False )
elif method == 'MST':
s = 'MST heuristic solution '
L, r = minSpanTree( self.problem, display=anim, animate=self.anim_route,\
wait_func=wait_func )
elif method == 'CHRISTO':
s = 'Christofides solution '
L, r = christofides( self.problem, display=anim, animate=self.anim_route,\
wait_func=wait_func )
elif method == 'LK':
s = 'Lin-Kernighan (Concorde) solution '
L, r = solveTSP( self.problem, exact=False, logFile=logFile )
elif method == 'CC':
s = 'Exact solution using Concorde '
L, r = solveTSP( self.problem, exact=True, logFile=self.logFile)
elif ('CPX' in method) or ('2CFF' in method):
# Apply Cplex to obtain an (optimal) solution
model = 'SCE' if 'CPX' in method else '2CF'
if model == '2CF' and 'SCE' in method: model='2CF-SCE'
lb, L, r = CPXtspSolve(self.problem, startRoute=self.broute, \
formulation=model, nodeLim=nodeLim, \
anim=anim, wait_func=wait_func,\
log_output=log_output )
s = "No feasible solution found. Lower bound="+str(lb) if r is None \
else "Cplex solution "
if r is None: self.lobnd = lb
if not s is None: self.sol_method = s
if not r is None:
self.route = r
self.routeLen = self.get_length(r) if L is None else L
if self.broute is None or self.brouteLen > L:
self.broute = self.route
self.brouteLen = L
def get_lobnd(self, method, log_output=False ):
"""
Compute lower bound on shortest route.
Parameters:
**method** : str
Indicates the method to compute the lower bound:
- OTREE for one tree lower bound
- FOTREE for the fast one tree lower bound
- LRTREE for 1-tree Lagrangian lower bound
- ASS for the assignment lower bound
- 2M for the 2-matching lower bound
- F2M for the fractional 2-matching lower bound
**log_output** : bool
If True, the Lagrangian method as well as methods
2M and F2M that use Cplex send messages to the screen.
"""
method.replace(" ","")
method = method.upper()
w = 0
elst = None
xvals = None
if method=='OTREE':
# Obtain 1-tree lower bound
w, elst = oneTree( self.problem )
s = "1-tree bound"
elif method=='FOTREE':
# Obtain fast 1-tree lower bound
w, elst = fast1Tree( self.problem )
s = "Reinelt's fast 1-tree bound"
elif method=='LRTREE':
# Obtain Lagrangian 1-tree lower bound
w, elst, _ = LR_1tree( self.problem, silent=not log_output )
s = "Lagrangian 1-tree bound"
elif method=='ASS':
# Obtain assignment lower bound
w, elst = assignLB( self.problem )
s = "Assignment lower bound"
elif method=='2M':
# Obtain 2-matching lower bound
w, elst = twoMatch( self.problem, log_output=log_output )
s = "2-matching lower bound"
elif method=='F2M':
# Obtain fractional 2-matching lower bound
w, elst, xvals = twoMatch( self.problem, fractional=True,\
log_output=log_output )
s = "Fractional 2-matching LB"
if not s is None: self.sol_method = s
if not w is None: self.lobnd = w
if not elst is None: self.elist = elst
self.xvals = xvals
#----------------------------------------------------------------------
def tsp_gui():
"""
Graphical user interface to methods from the class TSP.
"""
import tkinter as tk
from tkinter import messagebox
from tkinter import filedialog
from tkinter.simpledialog import askinteger
import sys, os
wmTitle = 'PyTSP - Methods for the TSP'
wmVersion =" Version "+__version__+" "
nodeLim = 1 # Node limit for Cplex solver
animCtl = None # Control variable animation on/off
logCtl = None # Control variable log output on/off
tsp = None # TSP instance
root = None # Main window
myText = None # Text widget for log output
menuBar = None # Main menu
plotMenu = None # Menu for plotting commands
# Class to redirect output
class RedirectText(object):
def __init__(self, text_ctrl):
self.output = text_ctrl
def write(self, string):
self.output.insert(tk.END,string)
def flush(self):
return
# Waiting function
def wait_tk():
plt.waitforbuttonpress(timeout=-1)
# On closing of the main window
def ask_closing():
if tk.messagebox.askokcancel("Quit", "Do you want to quit?"):
root.destroy()
# Command that does nothing
nothing = lambda : None
# Command for file menu
def openFile():
nonlocal tsp, menuBar, plotMenu
ftypes = [("TSP files","*.tsp")]
fname = filedialog.askopenfilename( parent=root,
title="Select data file", filetypes = ftypes )
if not fname is None and len(fname) > 0 and os.path.isfile(fname):
tsp = TSP(fname,interactive=False,no_wait=True)
if not tsp is None:
tsp.displayPoints()
menuBar.entryconfig("Solve",state="normal")
menuBar.entryconfig("Bound",state="normal")
menuBar.entryconfig("Plot",state="normal")
plotMenu.entryconfig("Plot solution", state="disabled")
plotMenu.entryconfig("Plot best solution", state="disabled")
plotMenu.entryconfig("Plot lowbound", state="disabled")
# Command for menu item "about"
about = lambda : tk.messagebox.showinfo(wmTitle, wmVersion )
def fix_nodeLim():
nonlocal nodeLim
prompt = "Current node limit is "+str(nodeLim)+". Enter new value:"
nLim = askinteger("Cplex node limit",prompt,minvalue=1)
if nLim is not None: nodeLim = nLim
def solve( method ):
if not tsp is None:
if not myText is None: myText.delete( "1.0", tk.END )
tsp.solve(method, anim=animCtl.get()>0, wait_func=wait_tk, nodeLim=nodeLim,\
log_output=logCtl.get()>0)
if not tsp.route is None:
plotMenu.entryconfig("Plot solution", state="normal")
plotMenu.entryconfig("Plot best solution", state="normal")
tsp.showSol()
def lobnd( method ):
if not tsp is None:
if not myText is None: myText.delete( "1.0", tk.END )
tsp.get_lobnd( method, log_output = logCtl.get()>0 )
if not tsp.elist is None:
plotMenu.entryconfig("Plot lowbound", state="normal")
tsp.showEdgeList()
# Command: Solve -> Nearest neighbor
solveNN = lambda : solve('NN')
# Command: Solve -> Nearest insertion
solveNI = lambda : solve('NI')
# Command: Solve -> Fartest insertion
solveFI = lambda : solve('FI')
# Command: Solve -> Min. span tree
solveMST = lambda : solve('MST')
# Command: Solve -> Christofides
solveCHRISTO = lambda : solve('CHRISTO')
# Command: Solve -> Lin-Kernighan
solveLK = lambda : solve('LK')
# Command: Solve -> Concorde
solveCC = lambda : solve('CC')
# Command: Solve -> Cplex
solveCPX = lambda : solve('CPX')
# Command: Solve -> Cplex 2CF formulation
solve2CFF = lambda : solve('2CFF')
# Command: Solve -> Cplex 2CF formulation with SCE cuts
solve2CFFSCE = lambda : solve('2CFFSCE')
# Command: Bound -> 1-tree
bnd1T = lambda : lobnd('OTREE')
# Command: Bound -> Fast 1-tree
bndF1T = lambda : lobnd('FOTREE')
# Command: Bound -> Lagrangian 1-tree
bndLR1T = lambda : lobnd('LRTREE' )
# Command: Bound -> Assignment
bndAss = lambda : lobnd('ASS')
# Command: Bound -> 2-matching
bnd2M = lambda : lobnd('2M')
# Commmand: Bound -> fractional 2-matching
bndF2M = lambda : lobnd('F2M' )
# Command: Plot points
plotP = lambda : None if tsp is None else tsp.displayPoints()
# Command: Plot solution
plotS = lambda : None if tsp is None or tsp.route is None else tsp.showSol()
# Command: Plot best solution
plotB = lambda : None if tsp is None or tsp.broute is None else tsp.showBestSol()
# Command: Plot lowbound (selected edges)
plotE = lambda : None if tsp is None or tsp.elist is None else tsp.showEdgeList()
# Initialize main window
root = tk.Tk()
root.protocol("WM_DELETE_WINDOW", ask_closing)
root.title(wmTitle)
root.minsize(400,300)
frame = tk.Frame(root)
frame.pack()
set_tk_window(root)
# If not run interatively, create a window for log output
if sys.stdin and sys.stdin.isatty():
logWin = None
else:
logWin = tk.Tk()
logWin.protocol("WM_DELETE_WINDOW", nothing )
logWin.title("PyTSP - log output")
logWin.geometry("400x300+300+300")
# Make a text element for output
myScroll = tk.Scrollbar(logWin)
myText = tk.Text(logWin, height=300, width=500)
myScroll.pack(side=tk.RIGHT, fill=tk.Y)
myText.pack(side=tk.LEFT, fill=tk.Y)
myScroll.config(command=myText.yview)
myText.config(yscrollcommand=myScroll.set)
# Redirect stdout to the text window
old_out = sys.stdout
sys.stdout = RedirectText(myText)
# Main menu
menuBar = tk.Menu(root,disabledforeground='grey')
# File menu
fileMenu = tk.Menu(menuBar, tearoff=0)
fileMenu.add_command(label="Open", underline=0, accelerator="O", command=openFile)
fileMenu.add_command(label="Exit", underline=1, accelerator="X", command=root.quit)
menuBar.add_cascade(label="File", underline=0, accelerator="Alt+F", menu=fileMenu)
# Menu item - Solve
solveMenu = tk.Menu(menuBar, tearoff=0 )
solveMenu.add_command(label="Nearest neighbour", underline=0, accelerator="N", command=solveNN)
solveMenu.add_command(label="Nearest insertion", underline=8, accelerator="I", command=solveNI)
solveMenu.add_command(label="Farthest insertion", underline=0, accelerator="F", command=solveFI)
solveMenu.add_command(label="Min. spanning tree", underline=0, accelerator="M", command=solveMST)
solveMenu.add_command(label="Christofides", underline=0, accelerator="C", command=solveCHRISTO)
solveMenu.add_command(label="Lin-Kernighan", underline=0, accelerator="L", command=solveLK)
solveMenu.add_command(label="Concorde B&C", underline=1, accelerator="O", command=solveCC)
solveMenu.add_command(label="CPLEX", underline=1, accelerator="P", command=solveCPX)
solveMenu.add_command(label="CPLEX-2CFF", underline=6, accelerator="2", command=solve2CFF)
solveMenu.add_command(label="2CFF with SCE cuts", underline=10, accelerator="S", command=solve2CFFSCE)
menuBar.add_cascade(label="Solve", underline=0, accelerator="Alt+S", menu=solveMenu)
menuBar.entryconfig("Solve",state='disabled')
# Menu item - Bound
bndMenu = tk.Menu(menuBar, tearoff=0 )
bndMenu.add_command(label='1-tree', underline=0,accelerator="1",command=bnd1T)
bndMenu.add_command(label='Fast 1-tree', underline=0,accelerator="F",command=bndF1T)
bndMenu.add_command(label='Lagrangian 1-tree', underline=0,accelerator="L",command=bndLR1T)
bndMenu.add_command(label='Assignment', underline=0,accelerator="A",command=bndAss)
bndMenu.add_command(label='2-matching', underline=0,accelerator="2",command=bnd2M)
bndMenu.add_command(label='2-matching (fract)', underline=2,accelerator="M",command=bndF2M)
menuBar.add_cascade(label="Bound", underline=0, accelerator="Alt+B", menu=bndMenu)
menuBar.entryconfig("Bound",state='disabled')
# Menu item - Plot
plotMenu = tk.Menu(menuBar, tearoff=0 )
plotMenu.add_command(label="Plot points", underline=0, accelerator="P",command=plotP)
plotMenu.add_command(label="Plot solution", underline=5, accelerator="S", command=plotS)
plotMenu.add_command(label="Plot best solution", underline=5, accelerator="B", command=plotB)
plotMenu.add_command(label='Plot lowbound', underline=5,accelerator="L",command=plotE)
menuBar.add_cascade(label="Plot",underline=0, accelerator="Alt+P", menu=plotMenu);
menuBar.entryconfig("Plot",state='disabled')
# Menu item - Options
optMenu = tk.Menu(menuBar, tearoff=0 )
animCtl = tk.IntVar()
animCtl.set(1)
optMenu.add_checkbutton(label='Animate',onvalue=1,offvalue=0,variable=animCtl)
logCtl = tk.IntVar()
logCtl.set(1)
optMenu.add_checkbutton(label='Log output',onvalue=1,offvalue=0,variable=logCtl)
optMenu.add_command(label="Node limit", underline=0, accelerator="N", command=fix_nodeLim)
menuBar.add_cascade(label="Options", underline=0, accelerator="Alt+O", menu=optMenu)
menuBar.add_command(label="About", underline=0, accelerator="Alt+A", command=about);
root.config(menu=menuBar)
root.mainloop()
if not logWin is None: sys.stdout = old_out
Sub-modules
tsp.concorde-
TSP - Python interface to Concorde - A C-library for solving TSPs …
tsp.tsp_cpx-
TSP - Solving the symmetric TSP by means of CPLEX's MIP solver and docplex
tsp.tsp_heu-
TSP - Some simple heuristics for the symmetric TSP.
tsp.tsp_hk-
TSP - Held and Karp (Lagrangian) lower bound for the symmetric TSP based on 1-trees.
tsp.tsp_match-
TSP - 2-matching and assignment lower bound for the symmetric TSP.
tsp.tsp_plot-
TSP - plotting routines.
tsp.tsp_trees-
TSP - Computation of 1-trees as relaxation of the symmetric TSP.
Functions
def default_wait()-
Default wait function used for waiting on user input/action to proceed with computations after plotting if Matplot.pyplot runs in interactive mode. The action is to click into the drawing window.
Expand source code
def default_wait(): """ Default wait function used for waiting on user input/action to proceed with computations after plotting if Matplot.pyplot runs in interactive mode. The action is to click into the drawing window. """ plt.waitforbuttonpress(timeout=-1) def tsp_gui()-
Graphical user interface to methods from the class TSP.
Expand source code
def tsp_gui(): """ Graphical user interface to methods from the class TSP. """ import tkinter as tk from tkinter import messagebox from tkinter import filedialog from tkinter.simpledialog import askinteger import sys, os wmTitle = 'PyTSP - Methods for the TSP' wmVersion =" Version "+__version__+" " nodeLim = 1 # Node limit for Cplex solver animCtl = None # Control variable animation on/off logCtl = None # Control variable log output on/off tsp = None # TSP instance root = None # Main window myText = None # Text widget for log output menuBar = None # Main menu plotMenu = None # Menu for plotting commands # Class to redirect output class RedirectText(object): def __init__(self, text_ctrl): self.output = text_ctrl def write(self, string): self.output.insert(tk.END,string) def flush(self): return # Waiting function def wait_tk(): plt.waitforbuttonpress(timeout=-1) # On closing of the main window def ask_closing(): if tk.messagebox.askokcancel("Quit", "Do you want to quit?"): root.destroy() # Command that does nothing nothing = lambda : None # Command for file menu def openFile(): nonlocal tsp, menuBar, plotMenu ftypes = [("TSP files","*.tsp")] fname = filedialog.askopenfilename( parent=root, title="Select data file", filetypes = ftypes ) if not fname is None and len(fname) > 0 and os.path.isfile(fname): tsp = TSP(fname,interactive=False,no_wait=True) if not tsp is None: tsp.displayPoints() menuBar.entryconfig("Solve",state="normal") menuBar.entryconfig("Bound",state="normal") menuBar.entryconfig("Plot",state="normal") plotMenu.entryconfig("Plot solution", state="disabled") plotMenu.entryconfig("Plot best solution", state="disabled") plotMenu.entryconfig("Plot lowbound", state="disabled") # Command for menu item "about" about = lambda : tk.messagebox.showinfo(wmTitle, wmVersion ) def fix_nodeLim(): nonlocal nodeLim prompt = "Current node limit is "+str(nodeLim)+". Enter new value:" nLim = askinteger("Cplex node limit",prompt,minvalue=1) if nLim is not None: nodeLim = nLim def solve( method ): if not tsp is None: if not myText is None: myText.delete( "1.0", tk.END ) tsp.solve(method, anim=animCtl.get()>0, wait_func=wait_tk, nodeLim=nodeLim,\ log_output=logCtl.get()>0) if not tsp.route is None: plotMenu.entryconfig("Plot solution", state="normal") plotMenu.entryconfig("Plot best solution", state="normal") tsp.showSol() def lobnd( method ): if not tsp is None: if not myText is None: myText.delete( "1.0", tk.END ) tsp.get_lobnd( method, log_output = logCtl.get()>0 ) if not tsp.elist is None: plotMenu.entryconfig("Plot lowbound", state="normal") tsp.showEdgeList() # Command: Solve -> Nearest neighbor solveNN = lambda : solve('NN') # Command: Solve -> Nearest insertion solveNI = lambda : solve('NI') # Command: Solve -> Fartest insertion solveFI = lambda : solve('FI') # Command: Solve -> Min. span tree solveMST = lambda : solve('MST') # Command: Solve -> Christofides solveCHRISTO = lambda : solve('CHRISTO') # Command: Solve -> Lin-Kernighan solveLK = lambda : solve('LK') # Command: Solve -> Concorde solveCC = lambda : solve('CC') # Command: Solve -> Cplex solveCPX = lambda : solve('CPX') # Command: Solve -> Cplex 2CF formulation solve2CFF = lambda : solve('2CFF') # Command: Solve -> Cplex 2CF formulation with SCE cuts solve2CFFSCE = lambda : solve('2CFFSCE') # Command: Bound -> 1-tree bnd1T = lambda : lobnd('OTREE') # Command: Bound -> Fast 1-tree bndF1T = lambda : lobnd('FOTREE') # Command: Bound -> Lagrangian 1-tree bndLR1T = lambda : lobnd('LRTREE' ) # Command: Bound -> Assignment bndAss = lambda : lobnd('ASS') # Command: Bound -> 2-matching bnd2M = lambda : lobnd('2M') # Commmand: Bound -> fractional 2-matching bndF2M = lambda : lobnd('F2M' ) # Command: Plot points plotP = lambda : None if tsp is None else tsp.displayPoints() # Command: Plot solution plotS = lambda : None if tsp is None or tsp.route is None else tsp.showSol() # Command: Plot best solution plotB = lambda : None if tsp is None or tsp.broute is None else tsp.showBestSol() # Command: Plot lowbound (selected edges) plotE = lambda : None if tsp is None or tsp.elist is None else tsp.showEdgeList() # Initialize main window root = tk.Tk() root.protocol("WM_DELETE_WINDOW", ask_closing) root.title(wmTitle) root.minsize(400,300) frame = tk.Frame(root) frame.pack() set_tk_window(root) # If not run interatively, create a window for log output if sys.stdin and sys.stdin.isatty(): logWin = None else: logWin = tk.Tk() logWin.protocol("WM_DELETE_WINDOW", nothing ) logWin.title("PyTSP - log output") logWin.geometry("400x300+300+300") # Make a text element for output myScroll = tk.Scrollbar(logWin) myText = tk.Text(logWin, height=300, width=500) myScroll.pack(side=tk.RIGHT, fill=tk.Y) myText.pack(side=tk.LEFT, fill=tk.Y) myScroll.config(command=myText.yview) myText.config(yscrollcommand=myScroll.set) # Redirect stdout to the text window old_out = sys.stdout sys.stdout = RedirectText(myText) # Main menu menuBar = tk.Menu(root,disabledforeground='grey') # File menu fileMenu = tk.Menu(menuBar, tearoff=0) fileMenu.add_command(label="Open", underline=0, accelerator="O", command=openFile) fileMenu.add_command(label="Exit", underline=1, accelerator="X", command=root.quit) menuBar.add_cascade(label="File", underline=0, accelerator="Alt+F", menu=fileMenu) # Menu item - Solve solveMenu = tk.Menu(menuBar, tearoff=0 ) solveMenu.add_command(label="Nearest neighbour", underline=0, accelerator="N", command=solveNN) solveMenu.add_command(label="Nearest insertion", underline=8, accelerator="I", command=solveNI) solveMenu.add_command(label="Farthest insertion", underline=0, accelerator="F", command=solveFI) solveMenu.add_command(label="Min. spanning tree", underline=0, accelerator="M", command=solveMST) solveMenu.add_command(label="Christofides", underline=0, accelerator="C", command=solveCHRISTO) solveMenu.add_command(label="Lin-Kernighan", underline=0, accelerator="L", command=solveLK) solveMenu.add_command(label="Concorde B&C", underline=1, accelerator="O", command=solveCC) solveMenu.add_command(label="CPLEX", underline=1, accelerator="P", command=solveCPX) solveMenu.add_command(label="CPLEX-2CFF", underline=6, accelerator="2", command=solve2CFF) solveMenu.add_command(label="2CFF with SCE cuts", underline=10, accelerator="S", command=solve2CFFSCE) menuBar.add_cascade(label="Solve", underline=0, accelerator="Alt+S", menu=solveMenu) menuBar.entryconfig("Solve",state='disabled') # Menu item - Bound bndMenu = tk.Menu(menuBar, tearoff=0 ) bndMenu.add_command(label='1-tree', underline=0,accelerator="1",command=bnd1T) bndMenu.add_command(label='Fast 1-tree', underline=0,accelerator="F",command=bndF1T) bndMenu.add_command(label='Lagrangian 1-tree', underline=0,accelerator="L",command=bndLR1T) bndMenu.add_command(label='Assignment', underline=0,accelerator="A",command=bndAss) bndMenu.add_command(label='2-matching', underline=0,accelerator="2",command=bnd2M) bndMenu.add_command(label='2-matching (fract)', underline=2,accelerator="M",command=bndF2M) menuBar.add_cascade(label="Bound", underline=0, accelerator="Alt+B", menu=bndMenu) menuBar.entryconfig("Bound",state='disabled') # Menu item - Plot plotMenu = tk.Menu(menuBar, tearoff=0 ) plotMenu.add_command(label="Plot points", underline=0, accelerator="P",command=plotP) plotMenu.add_command(label="Plot solution", underline=5, accelerator="S", command=plotS) plotMenu.add_command(label="Plot best solution", underline=5, accelerator="B", command=plotB) plotMenu.add_command(label='Plot lowbound', underline=5,accelerator="L",command=plotE) menuBar.add_cascade(label="Plot",underline=0, accelerator="Alt+P", menu=plotMenu); menuBar.entryconfig("Plot",state='disabled') # Menu item - Options optMenu = tk.Menu(menuBar, tearoff=0 ) animCtl = tk.IntVar() animCtl.set(1) optMenu.add_checkbutton(label='Animate',onvalue=1,offvalue=0,variable=animCtl) logCtl = tk.IntVar() logCtl.set(1) optMenu.add_checkbutton(label='Log output',onvalue=1,offvalue=0,variable=logCtl) optMenu.add_command(label="Node limit", underline=0, accelerator="N", command=fix_nodeLim) menuBar.add_cascade(label="Options", underline=0, accelerator="Alt+O", menu=optMenu) menuBar.add_command(label="About", underline=0, accelerator="Alt+A", command=about); root.config(menu=menuBar) root.mainloop() if not logWin is None: sys.stdout = old_out
Classes
class TSP (fname=None, problem=None, interactive=True, anim_route=False, no_wait=False, fontsize=6)-
Initialize instance of class TSP.
Parameters
fname : str, optional
None or the name of the input data file readable by module tsplib95. If fname is not None, the problem data is read from file fname using tsplib95.load(). Note that then "problem" is ignored even if it is not None.problem : class, optional
None or a tsp problem instance (cf. module tsplib95).interactive : bool, optional
If True and Matplotlib.pyplot is in non-interactive mode, pyplot is put into interactive mode. This then usually requires that after plotting something, a function is called to wait for user input/action. This is in this case, a click inside the window as long as the option no_wait is not True, otherwise there is no waiting after plotting. Default=True.anim_route : bool, optional
If True, Hamiltonian cycles are drawn in animated way, slowly edge by edge, if the solution is drawn/displayed. Otherwise, the cycle is just drawn if displayed.fontsize : int, optional
Size of font in drawings. Default = 6.Expand source code
class TSP: def __init__(self, fname=None, problem = None, interactive=True, anim_route=False, no_wait=False, fontsize=6 ): """ Initialize instance of class TSP. Parameters: **fname** : str, optional None or the name of the input data file readable by module tsplib95. If fname is not None, the problem data is read from file fname using tsplib95.load(). Note that then "problem" is ignored even if it is not None. **problem** : class, optional None or a tsp problem instance (cf. module tsplib95). **interactive** : bool, optional If True and Matplotlib.pyplot is in non-interactive mode, pyplot is put into interactive mode. This then usually requires that after plotting something, a function is called to wait for user input/action. This is in this case, a click inside the window as long as the option no_wait is not True, otherwise there is no waiting after plotting. Default=True. **anim_route** : bool, optional If True, Hamiltonian cycles are drawn in animated way, slowly edge by edge, if the solution is drawn/displayed. Otherwise, the cycle is just drawn if displayed. **fontsize** : int, optional Size of font in drawings. Default = 6. """ self.anim_route = anim_route """ Draw route in animated way or not""" self.fontsize = fontsize """Fontsize used in drawings""" self.one = 0.99999 """Approximation for 1""" self.problem = None """The problem instance (cf. tsplib95 for documentation)""" self.route = None """The sequence nodes are visited in current solution.""" self.routeLen = 0 """The length of the current route""" self.broute = None """Sequence of nodes as visited in best solution so far""" self.brouteLen = 0 """Length of best route found so far""" self.sol_method = "" """Name of the solution method that created the solution""" self.lobnd = None """A lower bound on the shortest route""" self.elist = None """A list of edges, e.g., in a minimum weight 1-tree""" self.xvals = None """Solution values to edge variables""" self.errMsg = "" self.logFile = 'nul' if 'Windows' in platform.system() else '/dev/null' self.wait = None if interactive and not plt.isinteractive(): if not no_wait: self.wait = default_wait plt.ion() if not fname is None: try: p = tl.load(fname) self.problem = p except: self.problem = None self.errMsg = "Unable to read data from file "+fname else: self.problem = problem p = self.problem if p is not None: # Set the weight function try: _ = p.wfunc # tsplib95 version before 0.7.1 except: self.problem.wfunc = p._wfunc # tsplib95, version 0.7.1 # Check if symmetric TSP if not p.is_symmetric(): if p.is_special() or self.really_asymmetric(): self.errMsg = "Cannot treat the asymmetric TSP." self.problem = None else: # Distance matrix is full matrix type. Change to lower row, # as otherwise stupid tsplib95 thinks it is asymmetric p.edge_weight_format = 'LOWER_ROW' if interactive and not plt.isinteractive(): plt.ion() if not interactive and plt.isinteractive(): plt.ioff() def really_asymmetric(self): """ Checks if distances in the TSP problem are asymmetric """ p = self.problem return max(abs(p.get_weight(e[0],e[1])-p.get_weight(e[1],e[0])) \ for e in combinat(p.get_nodes(),2)) > 0 def get_length(self, route): """ Compute length of route "route" """ if route is None or self.problem is None: return 0 p = self.problem L = sum(p.wfunc(route[i-1],route[i]) for i in range(1,p.dimension)) if route[0] != route[-1]: L += p.wfunc(route[-1],route[0]) return L def displayPoints(self): """ Plot the nodes/points appearing in the problem instance """ if self.problem.is_depictable(): displayPoints(self.problem, wait_func=self.wait) def showSol(self): """ Plot the route. """ if self.problem.is_depictable(): displayRoute(self.problem,self.route,self.routeLen,animate=self.anim_route,\ wait_func=self.wait, fontsize=self.fontsize,\ title=self.sol_method) else: print("Solution obtained by",self.sol_method) print(" Route length:",self.routeLen) print(" Route :",self.route) def showBestSol(self): """ Plot the best route found so far """ if self.problem.is_depictable(): displayRoute(self.problem,self.broute,self.brouteLen,animate=self.anim_route,\ wait_func=self.wait, fontsize=self.fontsize,\ title="Best solution found so far") else: print("Best solution found so far:") print(" Route length:",self.routeLen) print(" Route :",self.route) def showEdgeList( self ): """ Plot the edges selected in a relaxation that was solved to obtain a lower bound on the shortest route. Parameters: **xvals** : None or list of float If not None the (fractional) values of the edge variables in the solution to the relaxation. """ if self.problem.is_depictable(): info = self.sol_method + ". Lower bound: "+str(self.lobnd) elst = self.elist efract = None if not self.xvals is None: efract = [elst[i] for i in range(len(elst)) if self.xvals[i] < self.one] plotEdgeList( self.problem, elst, specialEdges=efract, title = info,\ fontsize=self.fontsize, wait_func=self.wait ) else: print("Lower bound :",self.lobnd) print("Edges selected:",self.elist) def solve( self, method, anim=False, wait_func=None, nodeLim=None, log_output=True ): """ Solve the problem instance using method "method!. The solution is stored in a list self.route that gives the sequence in which the nodes are visited and in a float (or int) called routeLen, the length of the route. Parameters: **method** : str Indicates the solution method to be applied and must be one of the following: - NN for nearest neighbour heuristic - NI for nearest insertion - FI for farthest insertion - MST for min. spanning tree heuristic - CHRISTO for Christofides' heuristic - LK for Concorde's Lin-Kernighan heuristic - CC for Concorde's exact branch-and-cut method - CPX for Cplex MIP solver - 2CFF for Cplex applied on the 2-commodity flow formulation - 2CFFSCE for 2-commodity flow + subcyle elimination cuts **anim** : bool If True, the solution method is run with animation active (as far as it has animation). **nodeLim** : int Limits the number of nodes that Cplex is going to enumerate If anim=True, it is strongly recommended to set the NodeLim to 1 so that just at the root node animated graphics are shown. **log_output** : bool If True, the default, and Cplex is used to solve the problem, Cplex sends messages on the solution progress to the screen. Remark: The methods that use Cplex (CPX, 2CFF, 2CFFSCE) makes use of the attributes "route" to set an initial start solution, provided of course route is not None. """ if anim and not self.problem.is_depictable(): anim=False method.replace(" ","") method = method.upper() logFile = None if log_output else self.logFile if anim and plt.isinteractive() and wait_func is None: wait_func = self.wait s, r, L = None, None, None if method == 'NN': s = 'Nearest neighbour route ' L, r = nearestNeighbour( self.problem ) elif method == 'NI': s = 'Nearest insertion route ' L, r = doInsertion( self.problem ) elif method == 'FI': s = 'Farthest insertion route ' L, r = doInsertion( self.problem, nearest=False ) elif method == 'MST': s = 'MST heuristic solution ' L, r = minSpanTree( self.problem, display=anim, animate=self.anim_route,\ wait_func=wait_func ) elif method == 'CHRISTO': s = 'Christofides solution ' L, r = christofides( self.problem, display=anim, animate=self.anim_route,\ wait_func=wait_func ) elif method == 'LK': s = 'Lin-Kernighan (Concorde) solution ' L, r = solveTSP( self.problem, exact=False, logFile=logFile ) elif method == 'CC': s = 'Exact solution using Concorde ' L, r = solveTSP( self.problem, exact=True, logFile=self.logFile) elif ('CPX' in method) or ('2CFF' in method): # Apply Cplex to obtain an (optimal) solution model = 'SCE' if 'CPX' in method else '2CF' if model == '2CF' and 'SCE' in method: model='2CF-SCE' lb, L, r = CPXtspSolve(self.problem, startRoute=self.broute, \ formulation=model, nodeLim=nodeLim, \ anim=anim, wait_func=wait_func,\ log_output=log_output ) s = "No feasible solution found. Lower bound="+str(lb) if r is None \ else "Cplex solution " if r is None: self.lobnd = lb if not s is None: self.sol_method = s if not r is None: self.route = r self.routeLen = self.get_length(r) if L is None else L if self.broute is None or self.brouteLen > L: self.broute = self.route self.brouteLen = L def get_lobnd(self, method, log_output=False ): """ Compute lower bound on shortest route. Parameters: **method** : str Indicates the method to compute the lower bound: - OTREE for one tree lower bound - FOTREE for the fast one tree lower bound - LRTREE for 1-tree Lagrangian lower bound - ASS for the assignment lower bound - 2M for the 2-matching lower bound - F2M for the fractional 2-matching lower bound **log_output** : bool If True, the Lagrangian method as well as methods 2M and F2M that use Cplex send messages to the screen. """ method.replace(" ","") method = method.upper() w = 0 elst = None xvals = None if method=='OTREE': # Obtain 1-tree lower bound w, elst = oneTree( self.problem ) s = "1-tree bound" elif method=='FOTREE': # Obtain fast 1-tree lower bound w, elst = fast1Tree( self.problem ) s = "Reinelt's fast 1-tree bound" elif method=='LRTREE': # Obtain Lagrangian 1-tree lower bound w, elst, _ = LR_1tree( self.problem, silent=not log_output ) s = "Lagrangian 1-tree bound" elif method=='ASS': # Obtain assignment lower bound w, elst = assignLB( self.problem ) s = "Assignment lower bound" elif method=='2M': # Obtain 2-matching lower bound w, elst = twoMatch( self.problem, log_output=log_output ) s = "2-matching lower bound" elif method=='F2M': # Obtain fractional 2-matching lower bound w, elst, xvals = twoMatch( self.problem, fractional=True,\ log_output=log_output ) s = "Fractional 2-matching LB" if not s is None: self.sol_method = s if not w is None: self.lobnd = w if not elst is None: self.elist = elst self.xvals = xvalsInstance variables
var anim_route-
Draw route in animated way or not
var broute-
Sequence of nodes as visited in best solution so far
var brouteLen-
Length of best route found so far
var elist-
A list of edges, e.g., in a minimum weight 1-tree
var fontsize-
Fontsize used in drawings
var lobnd-
A lower bound on the shortest route
var one-
Approximation for 1
var problem-
The problem instance (cf. tsplib95 for documentation)
var route-
The sequence nodes are visited in current solution.
var routeLen-
The length of the current route
var sol_method-
Name of the solution method that created the solution
var xvals-
Solution values to edge variables
Methods
def displayPoints(self)-
Plot the nodes/points appearing in the problem instance
Expand source code
def displayPoints(self): """ Plot the nodes/points appearing in the problem instance """ if self.problem.is_depictable(): displayPoints(self.problem, wait_func=self.wait) def get_length(self, route)-
Compute length of route "route"
Expand source code
def get_length(self, route): """ Compute length of route "route" """ if route is None or self.problem is None: return 0 p = self.problem L = sum(p.wfunc(route[i-1],route[i]) for i in range(1,p.dimension)) if route[0] != route[-1]: L += p.wfunc(route[-1],route[0]) return L def get_lobnd(self, method, log_output=False)-
Compute lower bound on shortest route.
Parameters
method : str
Indicates the method to compute the lower bound:
- OTREE for one tree lower bound
- FOTREE for the fast one tree lower bound
- LRTREE for 1-tree Lagrangian lower bound
- ASS for the assignment lower bound
- 2M for the 2-matching lower bound
- F2M for the fractional 2-matching lower boundlog_output : bool
If True, the Lagrangian method as well as methods 2M and F2M that use Cplex send messages to the screen.Expand source code
def get_lobnd(self, method, log_output=False ): """ Compute lower bound on shortest route. Parameters: **method** : str Indicates the method to compute the lower bound: - OTREE for one tree lower bound - FOTREE for the fast one tree lower bound - LRTREE for 1-tree Lagrangian lower bound - ASS for the assignment lower bound - 2M for the 2-matching lower bound - F2M for the fractional 2-matching lower bound **log_output** : bool If True, the Lagrangian method as well as methods 2M and F2M that use Cplex send messages to the screen. """ method.replace(" ","") method = method.upper() w = 0 elst = None xvals = None if method=='OTREE': # Obtain 1-tree lower bound w, elst = oneTree( self.problem ) s = "1-tree bound" elif method=='FOTREE': # Obtain fast 1-tree lower bound w, elst = fast1Tree( self.problem ) s = "Reinelt's fast 1-tree bound" elif method=='LRTREE': # Obtain Lagrangian 1-tree lower bound w, elst, _ = LR_1tree( self.problem, silent=not log_output ) s = "Lagrangian 1-tree bound" elif method=='ASS': # Obtain assignment lower bound w, elst = assignLB( self.problem ) s = "Assignment lower bound" elif method=='2M': # Obtain 2-matching lower bound w, elst = twoMatch( self.problem, log_output=log_output ) s = "2-matching lower bound" elif method=='F2M': # Obtain fractional 2-matching lower bound w, elst, xvals = twoMatch( self.problem, fractional=True,\ log_output=log_output ) s = "Fractional 2-matching LB" if not s is None: self.sol_method = s if not w is None: self.lobnd = w if not elst is None: self.elist = elst self.xvals = xvals def really_asymmetric(self)-
Checks if distances in the TSP problem are asymmetric
Expand source code
def really_asymmetric(self): """ Checks if distances in the TSP problem are asymmetric """ p = self.problem return max(abs(p.get_weight(e[0],e[1])-p.get_weight(e[1],e[0])) \ for e in combinat(p.get_nodes(),2)) > 0 def showBestSol(self)-
Plot the best route found so far
Expand source code
def showBestSol(self): """ Plot the best route found so far """ if self.problem.is_depictable(): displayRoute(self.problem,self.broute,self.brouteLen,animate=self.anim_route,\ wait_func=self.wait, fontsize=self.fontsize,\ title="Best solution found so far") else: print("Best solution found so far:") print(" Route length:",self.routeLen) print(" Route :",self.route) def showEdgeList(self)-
Plot the edges selected in a relaxation that was solved to obtain a lower bound on the shortest route.
Parameters
xvals : None or list of float
If not None the (fractional) values of the edge variables in the solution to the relaxation.Expand source code
def showEdgeList( self ): """ Plot the edges selected in a relaxation that was solved to obtain a lower bound on the shortest route. Parameters: **xvals** : None or list of float If not None the (fractional) values of the edge variables in the solution to the relaxation. """ if self.problem.is_depictable(): info = self.sol_method + ". Lower bound: "+str(self.lobnd) elst = self.elist efract = None if not self.xvals is None: efract = [elst[i] for i in range(len(elst)) if self.xvals[i] < self.one] plotEdgeList( self.problem, elst, specialEdges=efract, title = info,\ fontsize=self.fontsize, wait_func=self.wait ) else: print("Lower bound :",self.lobnd) print("Edges selected:",self.elist) def showSol(self)-
Plot the route.
Expand source code
def showSol(self): """ Plot the route. """ if self.problem.is_depictable(): displayRoute(self.problem,self.route,self.routeLen,animate=self.anim_route,\ wait_func=self.wait, fontsize=self.fontsize,\ title=self.sol_method) else: print("Solution obtained by",self.sol_method) print(" Route length:",self.routeLen) print(" Route :",self.route) def solve(self, method, anim=False, wait_func=None, nodeLim=None, log_output=True)-
Solve the problem instance using method "method!. The solution is stored in a list self.route that gives the sequence in which the nodes are visited and in a float (or int) called routeLen, the length of the route.
Parameters
method : str
Indicates the solution method to be applied and must be one of the following:
- NN for nearest neighbour heuristic
- NI for nearest insertion
- FI for farthest insertion
- MST for min. spanning tree heuristic
- CHRISTO for Christofides' heuristic
- LK for Concorde's Lin-Kernighan heuristic
- CC for Concorde's exact branch-and-cut method
- CPX for Cplex MIP solver
- 2CFF for Cplex applied on the 2-commodity flow formulation
- 2CFFSCE for 2-commodity flow + subcyle elimination cutsanim : bool
If True, the solution method is run with animation active (as far as it has animation).nodeLim : int
Limits the number of nodes that Cplex is going to enumerate If anim=True, it is strongly recommended to set the NodeLim to 1 so that just at the root node animated graphics are shown.log_output : bool
If True, the default, and Cplex is used to solve the problem, Cplex sends messages on the solution progress to the screen.Remark:
The methods that use Cplex (CPX, 2CFF, 2CFFSCE) makes use of the attributes "route" to set an initial start solution, provided of course route is not None.Expand source code
def solve( self, method, anim=False, wait_func=None, nodeLim=None, log_output=True ): """ Solve the problem instance using method "method!. The solution is stored in a list self.route that gives the sequence in which the nodes are visited and in a float (or int) called routeLen, the length of the route. Parameters: **method** : str Indicates the solution method to be applied and must be one of the following: - NN for nearest neighbour heuristic - NI for nearest insertion - FI for farthest insertion - MST for min. spanning tree heuristic - CHRISTO for Christofides' heuristic - LK for Concorde's Lin-Kernighan heuristic - CC for Concorde's exact branch-and-cut method - CPX for Cplex MIP solver - 2CFF for Cplex applied on the 2-commodity flow formulation - 2CFFSCE for 2-commodity flow + subcyle elimination cuts **anim** : bool If True, the solution method is run with animation active (as far as it has animation). **nodeLim** : int Limits the number of nodes that Cplex is going to enumerate If anim=True, it is strongly recommended to set the NodeLim to 1 so that just at the root node animated graphics are shown. **log_output** : bool If True, the default, and Cplex is used to solve the problem, Cplex sends messages on the solution progress to the screen. Remark: The methods that use Cplex (CPX, 2CFF, 2CFFSCE) makes use of the attributes "route" to set an initial start solution, provided of course route is not None. """ if anim and not self.problem.is_depictable(): anim=False method.replace(" ","") method = method.upper() logFile = None if log_output else self.logFile if anim and plt.isinteractive() and wait_func is None: wait_func = self.wait s, r, L = None, None, None if method == 'NN': s = 'Nearest neighbour route ' L, r = nearestNeighbour( self.problem ) elif method == 'NI': s = 'Nearest insertion route ' L, r = doInsertion( self.problem ) elif method == 'FI': s = 'Farthest insertion route ' L, r = doInsertion( self.problem, nearest=False ) elif method == 'MST': s = 'MST heuristic solution ' L, r = minSpanTree( self.problem, display=anim, animate=self.anim_route,\ wait_func=wait_func ) elif method == 'CHRISTO': s = 'Christofides solution ' L, r = christofides( self.problem, display=anim, animate=self.anim_route,\ wait_func=wait_func ) elif method == 'LK': s = 'Lin-Kernighan (Concorde) solution ' L, r = solveTSP( self.problem, exact=False, logFile=logFile ) elif method == 'CC': s = 'Exact solution using Concorde ' L, r = solveTSP( self.problem, exact=True, logFile=self.logFile) elif ('CPX' in method) or ('2CFF' in method): # Apply Cplex to obtain an (optimal) solution model = 'SCE' if 'CPX' in method else '2CF' if model == '2CF' and 'SCE' in method: model='2CF-SCE' lb, L, r = CPXtspSolve(self.problem, startRoute=self.broute, \ formulation=model, nodeLim=nodeLim, \ anim=anim, wait_func=wait_func,\ log_output=log_output ) s = "No feasible solution found. Lower bound="+str(lb) if r is None \ else "Cplex solution " if r is None: self.lobnd = lb if not s is None: self.sol_method = s if not r is None: self.route = r self.routeLen = self.get_length(r) if L is None else L if self.broute is None or self.brouteLen > L: self.broute = self.route self.brouteLen = L