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 10-12-2015 12:06 PM
(1210 views)

Hello,

I have been using PROC OPTNET to solve a traveling salesman problem. Now I want to solve an orienteering problem, which is a selective traveling salesman problem. Each node has a prize and the objective is maximize the total prize of the visited nodes within a time constraint. I cannot find any SAS documentation on this specific type of traveling salesman problem on how to solve it. Could someone please direct me?

1 ACCEPTED SOLUTION

Accepted Solutions

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

Here's one way, iterating between the MILP solver and the network (TSP) solver in a loop with PROC OPTMODEL. The master MILP problem prescribes which nodes to visit, and the TSP subproblem determines whether those nodes can be visited within the allotted time (or distance).

```
proc optmodel printlevel=0;
/* declare parameters and read data */
set NODES;
num x {NODES};
num y {NODES};
num score {NODES};
str name {NODES};
read data indata into NODES=[_N_] x y score name;
set ARCS = {i in NODES, j in NODES diff {i}};
num source;
for {i in NODES: score[i] = 0} do;
source = i;
leave;
end;
num distance {<i,j> in ARCS} =
(if j = source then 0 else sqrt((x[i]-x[j])^2+(y[i]-y[j])^2));
/* declare optimization model */
var UseNode {NODES} binary;
max TotalScore = sum {i in NODES} score[i] * UseNode[i];
num numsols init 0;
set SOLS = 1..numsols;
set NODES_s {SOLS};
con ExcludeSol {s in SOLS}:
sum {i in NODES_s[s]} UseNode[i] <= card(NODES_s[s]) - 1;
fix UseNode[source] = 1;
/* declare parameters used by network solver */
set TSP_NODES = {i in NODES: UseNode[i].sol > 0.5};
set <num,num> TOUR;
/* row generation loop */
do while (1);
/* call MILP solver */
put 'Solving MILP master...';
solve;
put TSP_NODES=;
/* call network (ATSP) solver */
put 'Solving ATSP subproblem...';
solve with network / TSP graph_direction=directed
subgraph=(nodes=TSP_NODES) links=(weight=distance) out=(tour=TOUR);
put TOUR=;
/* check feasibility and either exit loop or include new row */
if _NETWORK_OBJECTIVE_.sol <= &distance_budget then leave;
else do;
numsols = numsols + 1;
NODES_s[numsols] = TSP_NODES;
end;
end;
quit;
```

This version uses Euclidean distance, except that the distance back to the source node is 0.

7 REPLIES 7

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

Here's one way, iterating between the MILP solver and the network (TSP) solver in a loop with PROC OPTMODEL. The master MILP problem prescribes which nodes to visit, and the TSP subproblem determines whether those nodes can be visited within the allotted time (or distance).

```
proc optmodel printlevel=0;
/* declare parameters and read data */
set NODES;
num x {NODES};
num y {NODES};
num score {NODES};
str name {NODES};
read data indata into NODES=[_N_] x y score name;
set ARCS = {i in NODES, j in NODES diff {i}};
num source;
for {i in NODES: score[i] = 0} do;
source = i;
leave;
end;
num distance {<i,j> in ARCS} =
(if j = source then 0 else sqrt((x[i]-x[j])^2+(y[i]-y[j])^2));
/* declare optimization model */
var UseNode {NODES} binary;
max TotalScore = sum {i in NODES} score[i] * UseNode[i];
num numsols init 0;
set SOLS = 1..numsols;
set NODES_s {SOLS};
con ExcludeSol {s in SOLS}:
sum {i in NODES_s[s]} UseNode[i] <= card(NODES_s[s]) - 1;
fix UseNode[source] = 1;
/* declare parameters used by network solver */
set TSP_NODES = {i in NODES: UseNode[i].sol > 0.5};
set <num,num> TOUR;
/* row generation loop */
do while (1);
/* call MILP solver */
put 'Solving MILP master...';
solve;
put TSP_NODES=;
/* call network (ATSP) solver */
put 'Solving ATSP subproblem...';
solve with network / TSP graph_direction=directed
subgraph=(nodes=TSP_NODES) links=(weight=distance) out=(tour=TOUR);
put TOUR=;
/* check feasibility and either exit loop or include new row */
if _NETWORK_OBJECTIVE_.sol <= &distance_budget then leave;
else do;
numsols = numsols + 1;
NODES_s[numsols] = TSP_NODES;
end;
end;
quit;
```

This version uses Euclidean distance, except that the distance back to the source node is 0.

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

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

The closest parts of the formal documentation are probably these vehicle routing examples in which each vehicle visits a subset of nodes:

http://support.sas.com/documentation/cdl/en/ormpex/68157/HTML/default/viewer.htm#ormpex_ex23_toc.htm

http://support.sas.com/documentation/cdl/en/ormpex/68157/HTML/default/viewer.htm#ormpex_ex27_toc.htm

In each case, you can specialize to a single vehicle and modify the objective as needed.

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

Thank you again. I really appreciate your speedy responses.

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

Hi Rob,

Could you please explain the constraint in the given code? What exactly does it do?

```
con ExcludeSol {s in SOLS}:
sum {i in NODES_s[s]} UseNode[i] <= card(NODES_s[s]) - 1;
```

I also do not know what card(NODES_s[s] is. I don't see it defined anywhere.

Thanks

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

CARD returns the cardinality of a set:

The left-hand side of the constraint is a sum of binary variables, and the right-hand side is a constant that is one less than the number of binary variables. So the constraint "cuts off" a given solution by preventing all of the specified binary variables from being set to 1.

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

Registration is open! SAS is returning to Vegas for an AI and analytics experience like no other! Whether you're an executive, manager, end user or SAS partner, SAS Innovate is designed for everyone on your team. Register for just $495 by 12/31/2023.

**If you are interested in speaking, there is still time to submit a session idea. More details are posted on the website. **

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.