Turn on suggestions

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

Showing results for

Options

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

🔒 This topic is **solved** and **locked**.
Need further help from the community? Please
sign in and ask a **new** question.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Posted 12-08-2015 01:25 PM
(3557 views)

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

1 ACCEPTED SOLUTION

Accepted Solutions

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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;

12 REPLIES 12

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

Thank you for your time, it is really appreciated!

**SAS Innovate 2025** is scheduled for May 6-9 in Orlando, FL. Sign up to be **first to learn** about the agenda and registration!

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.