topic Re: I am failing to understand subtour elimination constraint. in Mathematical Optimization, Discrete-Event Simulation, and OR

I am failing to understand subtour elimination constraint.

V12DBS — Thu, 15 Jan 2015 23:18:58 GMT

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

Re: I am failing to understand subtour elimination constraint.

gergely_batho — Thu, 15 Jan 2015 23:56:44 GMT

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.

Re: I am failing to understand subtour elimination constraint.

V12DBS — Fri, 16 Jan 2015 03:24:03 GMT

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?

Re: I am failing to understand subtour elimination constraint.

RobPratt — Fri, 16 Jan 2015 03:53:02 GMT

You might find the following three documentation examples useful because they all demonstrate subtour elimination:

SAS/OR(R) 13.2 User's Guide: Mathematical Programming

SAS/OR(R) 13.2 User's Guide: Mathematical Programming Examples

Re: I am failing to understand subtour elimination constraint.

V12DBS — Fri, 16 Jan 2015 04:10:15 GMT

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?

Re: I am failing to understand subtour elimination constraint.

RobPratt — Fri, 16 Jan 2015 04:24:01 GMT

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.

Re: I am failing to understand subtour elimination constraint.

V12DBS — Fri, 16 Jan 2015 05:03:33 GMT

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.