Issue with Subtour Elimination Callback

Hello,

I was trying to handle the subtour issue inside a complex network design problem through adding subtour elimination cuts via the Callback. However, the procedure does not seem to work. As the B&C keeps identifying the same "tour" which was supposed to be eliminated in the previous iteration. I am wondering if there is any error in my Callback code. Your help is greatly appreciated!

Below is the code of the Callback:

def SubtourCallback (model, where):
if where == GRB.Callback.MIPSOL:
#make a list of drone arcs selected in the solution
vals = model.cbGetSolution(model._vars)
selected = gp.tuplelist((i,j) for (i,j,m) in ArcsM if m == 'droneS' and vals[i,j,m] > 0.5)
print("selected arcs: ", selected)
G = nx.DiGraph()
for a in selected:
G.add_edge(*a)
print("arc in the graph: ", list(G.edges))
#print("vertices with selected arcs: ", list(G.nodes))
try:
#print("tour found: ", list(nx.find_cycle(G)))
tour = []
for a in list(nx.find_cycle(G)):
tour.append((a[0], a[1], 'droneS'))
print("tour found: ", tour)
#turn tour into a list of nodes representing the cycle
cycle = []
for a in tour:
cycle.append(a[0])
print("list of nodes in cycle: ", cycle)
model.cbLazy(gp.quicksum(model._vars[i,j,'droneS'] for i,j in combinations(cycle, 2) if (i,j,'droneS') in ArcsM) <= len(cycle)-1)
print("Cuts are added!")
except nx.NetworkXError:
print ("No cycle in the solution")

The output log is provided below, where you can see the same tour keeps coming up, although it was supposed to be cut off in the prior iterations. 

selected arcs: <gurobi.tuplelist (7 tuples, 2 values each):
( 1 , 5 )
( 1 , 6 )
( 5 , 11 )
( 8 , 12 )
( 8 , 13 )
( 11 , 1 )
( 11 , 8 )
>
arc in the graph: [(1, 5), (1, 6), (5, 11), (11, 1), (11, 8), (8, 12), (8, 13)]
tour found: [(1, 5, 'droneS'), (5, 11, 'droneS'), (11, 1, 'droneS')]
list of nodes in cycle: [1, 5, 11]

Cuts are added!
H 0 0 11275.200000 9462.12438 16.1% - 2s
0 0 9462.12438 0 12 11275.2000 9462.12438 16.1% - 2s
0 0 9462.12438 0 41 11275.2000 9462.12438 16.1% - 2s
0 0 9462.12438 0 47 11275.2000 9462.12438 16.1% - 2s
0 0 9462.12438 0 51 11275.2000 9462.12438 16.1% - 2s
0 0 9462.12438 0 57 11275.2000 9462.12438 16.1% - 2s
0 0 9498.28634 0 59 11275.2000 9498.28634 15.8% - 2s
0 0 9499.36854 0 58 11275.2000 9499.36854 15.7% - 2s
0 0 9540.63931 0 58 11275.2000 9540.63931 15.4% - 2s
0 0 9540.63931 0 58 11275.2000 9540.63931 15.4% - 2s
0 2 9550.14808 0 58 11275.2000 9550.14808 15.3% - 2s
selected arcs: <gurobi.tuplelist (8 tuples, 2 values each):
( 1 , 5 )
( 1 , 6 )
( 1 , 7 )
( 7 , 11 )
( 8 , 12 )
( 8 , 13 )
( 8 , 1 )
( 11 , 8 )
>
arc in the graph: [(1, 5), (1, 6), (1, 7), (7, 11), (11, 8), (8, 12), (8, 13), (8, 1)]
tour found: [(1, 7, 'droneS'), (7, 11, 'droneS'), (11, 8, 'droneS'), (8, 1, 'droneS')]
list of nodes in cycle: [1, 7, 11, 8]

Cuts are added!
H 31 32 11218.000000 9802.80606 12.6% 59.6 2s
selected arcs: <gurobi.tuplelist (8 tuples, 2 values each):
( 1 , 5 )
( 1 , 6 )
( 1 , 7 )
( 5 , 11 )
( 8 , 12 )
( 8 , 13 )
( 11 , 1 )
( 11 , 8 )
>
arc in the graph: [(1, 5), (1, 6), (1, 7), (5, 11), (11, 1), (11, 8), (8, 12), (8, 13)]
tour found: [(1, 5, 'droneS'), (5, 11, 'droneS'), (11, 1, 'droneS')]
list of nodes in cycle: [1, 5, 11]

Cuts are added!
H 71 57 11170.000000 9802.80606 12.2% 42.5 2s
selected arcs: <gurobi.tuplelist (7 tuples, 2 values each):
( 1 , 5 )
( 1 , 6 )
( 5 , 11 )
( 8 , 12 )
( 8 , 13 )
( 11 , 1 )
( 11 , 8 )
>
arc in the graph: [(1, 5), (1, 6), (5, 11), (11, 1), (11, 8), (8, 12), (8, 13)]
tour found: [(1, 5, 'droneS'), (5, 11, 'droneS'), (11, 1, 'droneS')]
list of nodes in cycle: [1, 5, 11]

Cuts are added!
H 75 57 10885.200000 9802.80606 9.94% 42.1 2s
selected arcs: <gurobi.tuplelist (10 tuples, 2 values each):
( 1 , 5 )
( 1 , 6 )
( 1 , 12 )
( 1 , 13 )
( 2 , 8 )
( 6 , 7 )
( 6 , 11 )
( 8 , 11 )
( 8 , 1 )
( 6 , 2 )
>
arc in the graph: [(1, 5), (1, 6), (1, 12), (1, 13), (6, 7), (6, 11), (6, 2), (2, 8), (8, 11), (8, 1)]
tour found: [(1, 6, 'droneS'), (6, 2, 'droneS'), (2, 8, 'droneS'), (8, 1, 'droneS')]
list of nodes in cycle: [1, 6, 2, 8]

Cuts are added!
* 216 175 53 10640.400000 9802.80606 7.87% 25.8 2s

Haitao Li

University of Missouri - St. Louis