Subtour Elimination constraint with the RHS not equal to |S|-1
This is my subtler elimination constraint. On the RHS, I have |S|-r(S), where r(S) is a dictionary that collects the minimum number of vehicles needed for each subset of nodes.
I have my my subtour and subtourelim function the same as the TSP example. I kind of know I need to modify it futher, but don't know how to move forward.
May I get some help on this? Thank you!
# Callback - use lazy constraints to eliminate sub-tours
def subtourelim(model, where):
if where == GRB.Callback.MIPSOL:
# make a list of edges selected in the solution
vals = model.cbGetSolution(model._vars)
selected = gp.tuplelist((i, j) for i, j in model._vars.keys()
if vals[i, j] > 0.5)
# find the shortest cycle in the selected edge list
tour = subtour(selected)
if len(tour) < len(V_index):
# add subtour elimination constr. for every pair of cities in subtour
model.cbLazy(gp.quicksum(model._vars[i, j] for i, j in combinations(tour, 2))
<= len(tour)-1)
# Given a tuplelist of edges, find the shortest subtour
def subtour(edges):
unvisited = V_index[:]
cycle = V_index[:] # Dummy - guaranteed to be replaced
while unvisited: # true if list is non-empty
thiscycle = []
neighbors = unvisited
while neighbors:
current = neighbors[0]
thiscycle.append(current)
unvisited.remove(current)
neighbors = [j for i, j in edges.select(current, '*')
if j in unvisited]
if len(thiscycle) <= len(cycle):
cycle = thiscycle # New shortest subtour
return cycle
def subtourelim(model, where):
if where == GRB.Callback.MIPSOL:
# make a list of edges selected in the solution
vals = model.cbGetSolution(model._vars)
selected = gp.tuplelist((i, j) for i, j in model._vars.keys()
if vals[i, j] > 0.5)
# find the shortest cycle in the selected edge list
tour = subtour(selected)
if len(tour) < len(V_index):
# add subtour elimination constr. for every pair of cities in subtour
model.cbLazy(gp.quicksum(model._vars[i, j] for i, j in combinations(tour, 2))
<= len(tour)-1)
# Given a tuplelist of edges, find the shortest subtour
def subtour(edges):
unvisited = V_index[:]
cycle = V_index[:] # Dummy - guaranteed to be replaced
while unvisited: # true if list is non-empty
thiscycle = []
neighbors = unvisited
while neighbors:
current = neighbors[0]
thiscycle.append(current)
unvisited.remove(current)
neighbors = [j for i, j in edges.select(current, '*')
if j in unvisited]
if len(thiscycle) <= len(cycle):
cycle = thiscycle # New shortest subtour
return cycle
m._vars = vars
m.Params.lazyConstraints = r
m.optimize(subtourelim)
0
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
Post is closed for comments.
Comments
1 comment