# 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

Please sign in to leave a comment.

## Comments

0 comments