SAS Optimization, and SAS Simulation Studio

turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Find a Community

Topic Options

- RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

01-15-2015 06:18 PM

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

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to V12DBS

01-15-2015 11:24 PM

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.

All Replies

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to V12DBS

01-15-2015 06:56 PM

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.

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to gergely_batho

01-15-2015 10:24 PM

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?

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to V12DBS

01-15-2015 10:53 PM

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

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

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to RobPratt

01-15-2015 11:10 PM

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

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to V12DBS

01-15-2015 11:24 PM

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.

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to RobPratt

01-16-2015 12:03 AM

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.