Operations Research topics: SAS/OR,
SAS Optimization, and SAS Simulation Studio

I am failing to understand subtour elimination constraint.

Accepted Solution Solved
Reply
Occasional Contributor
Posts: 11
Accepted Solution

I am failing to understand subtour elimination constraint.

Can someone help me understand it? Also will a subtour elimination constraint required for a multi depot VRP with backhaul?


Accepted Solutions
Solution
‎01-15-2015 11:24 PM
SAS Employee
Posts: 448

Re: I am failing to understand subtour elimination constraint.

Suppose the depot is node 0 and your solution satisfies x[2,5] = 1, x[5,8] = 1, and x[8,2] = 1.  Then this solution contains a subtour of length 3.  Disallowing x[i,j] with i = j eliminates only subtours of length 1 but allows longer subtours.  So you need constraints to eliminate them.

The pictures in the first (TSP) example should help solidify the concept.  You want a single connected tour that contains each node exactly once.  But the first several iterations of the algorithm yield a collection of disjoint subtours that together contain each node exactly once.  The subtour elimination constraints prevent such subtours from arising, and these constraints are added to the problem dynamically.  Once you get a solution that is a single tour, you terminate the algorithm.

View solution in original post


All Replies
SAS Employee
Posts: 340

Re: I am failing to understand subtour elimination constraint.

If your model is a direct extension of a "classical" TSP model or a "classical" VRP moddel, then yes.

Without those constraints the solution will contain subtours: circular paths, that have no connections to the depot(s).

Of course a depot-node should not be part of such a constraint, becasuse a circle containing a depot is a valid tour.

Occasional Contributor
Posts: 11

Re: I am failing to understand subtour elimination constraint.

Thanks very much for the reply Gergely. If I have a decision variable X(i,j) where i != j, then how will I have circular paths even if I do not have a sub tour elimination constraint?

SAS Employee
Posts: 448

Re: I am failing to understand subtour elimination constraint.

Occasional Contributor
Posts: 11

Re: I am failing to understand subtour elimination constraint.

Hi Rob,

Thanks for the reply. The examples are great but are a bit overwhelming since I do not understand the fundamentals of subtour. I feel like I am chasing tail when I try to understand the concept. (just like the circular route without subtours)

How would you explain subtours to a person who is struggling to understand the concept? Like I said how would I have a circular route without going to a depot if my decision variables do not have i = j?

Solution
‎01-15-2015 11:24 PM
SAS Employee
Posts: 448

Re: I am failing to understand subtour elimination constraint.

Suppose the depot is node 0 and your solution satisfies x[2,5] = 1, x[5,8] = 1, and x[8,2] = 1.  Then this solution contains a subtour of length 3.  Disallowing x[i,j] with i = j eliminates only subtours of length 1 but allows longer subtours.  So you need constraints to eliminate them.

The pictures in the first (TSP) example should help solidify the concept.  You want a single connected tour that contains each node exactly once.  But the first several iterations of the algorithm yield a collection of disjoint subtours that together contain each node exactly once.  The subtour elimination constraints prevent such subtours from arising, and these constraints are added to the problem dynamically.  Once you get a solution that is a single tour, you terminate the algorithm.

Occasional Contributor
Posts: 11

Re: I am failing to understand subtour elimination constraint.

Rob,

Thanks a ton for being patient with me and a very big thanks. Pointing me to the picture and the word "disjoint" absolutely nailed it. This is exactly what I was seeking.

Now I will enjoy reading more about subtours and implement it in my model.

🔒 This topic is solved and locked.

Need further help from the community? Please ask a new question.

Discussion stats
  • 6 replies
  • 5353 views
  • 6 likes
  • 3 in conversation