# Subtour elimination for directed graph with repeated vertices allowed.

My classmates and I are trying to model a problem where a driver takes a tour around a directed graph, dropping off passengers. The driver can either drop passengers off directly at their destination, or drop them off and the passenger will take the shortest path to their destination from the drop off node. It takes less energy to drive than it does to walk, but the car may have to backtrack. Moreover, the driver must return to the source node. We're looking for the min-cost tour. We're working on modeling this with an MIP, however, we're having a lot of trouble with the subtour elimination constraint. We're using a lazy constraint for subtour elimination, that starts by finding the smallest selected subtour, S. What we want to do then, is say "If S has any internal edges, then it must have at least one outgoing edge", but we are having trouble figuring out how to encode this logic. We of course only want to force the outgoing edge constraint in the case that an internal edge in S is used in a given solution. We can't figure out a way to express this in a linear constraint. Quadratic constraints may be ok as well, but I'm not sure that Gurobi supports lazy quadratic constraints. Thanks so much for any insight!

Please sign in to leave a comment.

## Comments

0 comments