SCOP is a constrained programming solver.
In the example we call SCOP from Python language.
In the graph the number is the distances between locations and the green line is the optimal solution.
The problem is to find a shortest possible tour that visits each location exactly once.
The Python code can be written as follows:
************************************
"""
tsp-scop.py:
Using SCOP for solving the traveling salesman problem
Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2011
"""
from scop2 import *
m=Model()
cities=["T","L","M","R","B"]
d=[[0,476,774,434,408],[476,0,784,894,569],[774,784,0,852,1154],[434,894,852,0,569],[408,569,1154,569,0]]
n=len(cities)
varlist=m.addVariables(cities,range(n))
con1=Alldiff("AD",varlist,"inf")
m.addConstraint(con1)
obj=Quadratic("obj")
for i in range(n):
for j in range(n):
if i!=j:
for k in range(n):
if k ==n-1:
ell=0
else:
ell=k+1
obj.addTerms(d[i][j],varlist[i],k,varlist[j],ell)
m.addConstraint(obj)
m.Params.TimeLimit=1
sol,violated=m.optimize()
print "solution"
for x in sol:
print x,sol[x]
print "violated constraint(s)"
for v in violated:
print v,violated[v]
************************************
We get the following result:
************************************
##solution
##B 2
##R 0
##M 4
##T 1
##L 3
##violated constraint(s)
##obj 3047
************************************
