# source:projects/Dippy/trunk/examples/tsp.py@310

Last change on this file since 310 was 310, checked in by smitchell, 3 years ago

moved to a coinor.dippy namespace and cleaned up the setup.py

File size: 3.5 KB
Line
1from pulp import *
2import coin.dippy as dippy
3from math import sqrt
4
5# 2d Euclidean TSP with extremely simple cut generation
6
7# x,y coords of cities
8CITY_LOCS = [(0, 2), (0, 4), (1, 2), (1, 4), \
9             (4, 1), (4, 4), (4, 5),  (5, 0), \
10             (5, 2), (5, 5)]
11CITIES = range(len(CITY_LOCS))
12
13ARCS = [] # list of arcs (no duplicates)
14ARC_COSTS = {} # distance
15
16# for each city, list of arcs into/out of
17CITY_ARCS = [[] for i in CITIES]
18
19# use 2d euclidean distance
20def dist(x1, y1, x2, y2):
21    return sqrt((x1-x2)**2 + (y1-y2)**2)
22
23# construct list of arcs
24for i in CITIES:
25    i_x, i_y = CITY_LOCS[i]
26    for j in CITIES[i+1:]:
27        j_x, j_y = CITY_LOCS[j]
28        ARC_COSTS[(i,j)] = dist(i_x, i_y, j_x, j_y)
29        ARCS.append((i, j))
30        CITY_ARCS[i].append((i, j))
31        CITY_ARCS[j].append((i, j))
32
33prob = dippy.DipProblem()
34
35arc_vars = LpVariable.dicts("UseArc", ARCS, 0, 1, LpBinary)
36
37# objective
38prob += lpSum(ARC_COSTS[x] * arc_vars[x] for x in ARCS)
39
40# degree constraints
41for city in CITIES:
42    prob += lpSum(arc_vars[x] for x in CITY_ARCS[city]) \
43            == 2
44
45# generate subtour elimination constraints
46
47# dictionary for symmetric arcs, can be
48# accessed using (i, j) and (j, i)
49symmetric = {}
50for i in CITIES:
51    for j in CITIES:
52        if i < j:
53            symmetric[(i, j)] = (i, j)
54            symmetric[(j, i)] = (i, j)
55
56def generate_cuts(prob, sol):
57    cons = []
58    not_connected = set(CITIES)
59
60    while not_connected:
61 #       print "not_connected", [n for n in not_connected]
62        start = not_connected.pop()
63        nodes, arcs = get_subtour(sol, start)
64        if len(nodes) == len(arcs) and \
65           len(nodes) < len(CITIES):
66            cons.append( lpSum(arc_vars[a] for a in arcs) \
67                         <= len(arcs) - 1 )
68 #       print "nodes", [n for n in nodes]
69 #       print "arcs", [a for a in arcs]
70        nodes.remove(start)
71        not_connected -= nodes
72
73    print "# cons = ", len(cons)
74    print "cons = ", [ con for con in cons ]
75    return cons
76prob.generate_cuts = generate_cuts
77
78def is_solution_feasible(prob, sol):
79    nodes, arcs = get_subtour(sol, 0)
80#    print "Checking: # nodes = ", len(nodes), ", # cities = ", len(CITIES)
81#    print "nodes", [n for n in nodes]
82
83    return len(nodes) == len(arcs) and \
84           len(nodes) == len(CITIES)
85prob.is_solution_feasible = is_solution_feasible
86
87def get_subtour(sol, node):
88    # returns: list of nodes and arcs
89    # in subtour containing node
90    nodes = set([node])
91    arcs = set([])
92    not_processed = set(CITIES)
93    to_process = set([node])
94
95    tol = 1e-6
96    one = 1 - tol
97
98    while to_process:
99        c = to_process.pop()
100        not_processed.remove(c)
101        new_arcs = [ symmetric[(c, i)] \
102                     for i in not_processed \
103                     if sol[ \
104                         arc_vars[symmetric[(c, i)]]]
105                     > one]
106        new_nodes = [ i for i in not_processed \
107                      if symmetric[(i, c)] in new_arcs ]
108 #       print "new_nodes", [n for n in new_nodes]
109 #       print "new_arcs", [a for a in new_arcs]
110        arcs |= set(new_arcs)
111        nodes |= set(new_nodes)
112        to_process |= set(new_nodes)
113 #       print "not_processed", [n for n in not_processed]
114 #       print "nodes", [n for n in nodes]
115 #       print "arcs", [a for a in arcs]
116
117    return nodes, arcs
118
119dippy.Solve(prob, {
120    'DECOMP': {
121        'CutCGL': '0',
122    },
123})
124
125# print solution
126for arc, var in arc_vars.items():
127    if var.varValue:
128        print arc, var.varValue
Note: See TracBrowser for help on using the repository browser.