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

12-08-2015 01:25 PM

Greetings,

I would like to write an algorithm that would minimize the distance to travel a series of roads. In input, I have the longitude and latitude of the beginning and the end of each road. This problem looks like the Traveling Salesman Problem (https://en.wikipedia.org/wiki/Travelling_salesman_problem) or the Route inspection Problem (https://en.wikipedia.org/wiki/Route_inspection_problem).

However, I have to pass through each one of these roads and backtracking is inevitable (there are some dead-ends). I found the optnet procedure on SAS help, but I cannot resolve my problem, because the TSP hypothesis is to pass once per point and only undirected graphs are accepted.

I tried to use the beginning of each roads as points, but it is not working as intended. I would appreciate any help.

Thanks,

Marc-Antoine

Message 1 of 13
(943 Views)

Accepted Solutions

Solution

02-19-2016
01:55 PM

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

Posted in reply to Ceciestunnomtemporaire

12-18-2015 04:41 PM

For network problems, adding dummy nodes and arcs with high cost is the usual approach to diagnose infeasibility, as you have described. But since you are having trouble with that approach, you might consider using the IIS detection feature that diagnoses infeasibility for linear programming problems:

This method requires an explicit LP formulation, and you can use the code in the following example, which solves a generic minimum-cost network flow problem:

You should replace the SOLVE statement with:

solve with LP / iis=on;

expand / iis;

All Replies

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

Posted in reply to Ceciestunnomtemporaire

12-09-2015 10:00 AM

Can you please share your data and code, or at least some sample data?

By the way, although your problem is not TSP, note that the TSP algorithm supports directed graphs in SAS/OR 14.1:

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

Posted in reply to RobPratt

12-09-2015 10:24 AM

My data looks like this:

data have;

input road_id $ length longitude_begin latitude_begin longitude_end latitude_end class $15.;

cards ;

H1 5000 -70.1 45.2 -70.3 45.1 Highway

H2 5200 -70.3 45.1 -70.5 45.3 Highway

H3 4200 -70.5 45.3 -70.6 45.7 Highway

R1 1200 -71.4 45.0 -71.3 45.1 Contiguous

R2 1000 -71.3 45.1 -71.2 45.1 Contiguous

;

run;

Of course there are way more than that (average of 2000 roads ID per group). In this example, the roads H1, H2 and H3 are connected and can be used in 1 direction only. The roads R1 and R2 and connected and can be used in both directions.

Thanks for your time !

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

Posted in reply to Ceciestunnomtemporaire

12-09-2015 02:35 PM

As described in Application 19.14 of *Network Flows* (Ahuja, Magnanti, Orlin), the directed version of the problem can be formulated as a minimum-cost network flow problem with 0 supply at each node and a lower bound of 1 unit of flow on each arc. You can use either PROC OPTNET...

...or the network solver in PROC OPTMODEL:

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

Posted in reply to RobPratt

12-10-2015 08:11 AM

I don't understand exactly how the problem is working. If the supply is at 0, does it mean there is no limit ? I am trying to write a simple example, but it does not compute...

Howerer, I thought of something else. I used the "Shortpath" statement in the Optnet procedure. It is giving me the shortest path between every pair of points I have in my data. I then use the number of nodes between each Source/sink as the weight for the TSP problem based on those paths. It's like creating fictive edges so that I can use each nodes more than once.

Right now, I am using SAS 9.3, so I cannot use the directed version of the problem, but the results are great. It covers a great part of the network. We might switch to 9.4 soon and I think that I would be able to solve the majority of my problem with this version.

Thanks !

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

Posted in reply to Ceciestunnomtemporaire

12-10-2015 11:30 AM

Supply of 0 at a node just forces inflow to be equal to outflow at that node. There is no upper bound for the flow on each arc, but the minimization objective will drive it to be as small possible, according to the arc costs. If you post your simple example, I'll take a look. One thing you might have missed is that the two-way arcs should be replaced with two one-way arcs in the input data.

The undirected version of the problem is addressed in Application 19.15 of *Network Flows*. The solution approach does compute all-pairs shortest paths as the first step (as you mentioned), and this is also available in PROC OPTNET or PROC OPTMODEL. Note here that the shortest paths are with respect to the sum of arc distances, not the number of arcs. But the second step is a weighted matching problem on a complete graph consisting of the odd-degree nodes, where the new cost of edge (i,j) is the shortest path distance between i and j in the original graph. You can solve this problem by using the MILP solver in PROC OPTMODEL. There is a binary decision variable for each edge, and if the solver returns a value of 1 for edge (i,j), it means that all the arcs in the shortest path between i and j in the original network should be added. In fact, you can call the network solver and then the MILP solver in the same PROC OPTMODEL session.

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

Posted in reply to RobPratt

12-18-2015 02:38 PM

Thanks, this is helping me a lot. Is is working for a great number of my groups.

Just to know, is there a way to know why is the problem infeasible ? I am dividing my groups by connected components, but the ones with greater number of nodes are not running and the problem is said infeasible, and I do not find why.

The first thing I could think is my network need more links between the set of nodes, but I already added "fake links" to each pair of nodes. If I could find a way to find the nodes I need to remove or the links I need to add to be able to have a feasible problem, that would be interesting.

Solution

02-19-2016
01:55 PM

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

Posted in reply to Ceciestunnomtemporaire

12-18-2015 04:41 PM

For network problems, adding dummy nodes and arcs with high cost is the usual approach to diagnose infeasibility, as you have described. But since you are having trouble with that approach, you might consider using the IIS detection feature that diagnoses infeasibility for linear programming problems:

This method requires an explicit LP formulation, and you can use the code in the following example, which solves a generic minimum-cost network flow problem:

You should replace the SOLVE statement with:

solve with LP / iis=on;

expand / iis;

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

Posted in reply to RobPratt

02-19-2016 01:55 PM - edited 02-19-2016 02:02 PM

Thanks for the tips, it helped me a lot.

However, for some groups, I am having an error and I can't find and solution on google. The error is:

ERROR: objValue:12356273 objValueLB:12356273

I think it may be an error of memory (the value is ~~the the~~ not the same every time). I tried some options, but the problem is still happening. Do you have an idea of where it might come from?

Thanks !

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

Posted in reply to Ceciestunnomtemporaire

02-19-2016 02:27 PM

Can you please attach data and code for one of the groups that yields this error?

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

Posted in reply to RobPratt

02-19-2016 03:06 PM

The example is joined (names have been changed) and the code I'm using is:

```
proc optnet
graph_direction=directed
/*loglevel = none*/
data_links = optimize;
/* out_nodes = not_test_out2;*/
tsp out = Test_out2 cutstrategy=2 emphasis=1 HEURISTICS=3 CONFLICTSEARCH=2;
run;
```

I've tried with and without the TSP options, but it's not different.

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

Posted in reply to Ceciestunnomtemporaire

02-20-2016 12:17 PM

I am able to replicate this behavior, and it turns out to be a known issue in the TSP solver when the objective value is large. It will be fixed in the next release, but as a workaround you can scale the input weights by dividing by 1000. Doing so averted the issue for me.

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

Posted in reply to RobPratt

02-22-2016 11:34 AM

Yes, it worked for me too and for my other groups I had problems.

Thank you for your time, it is really appreciated!