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

- Subscribe to 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
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

10-12-2015 12:06 PM - edited 10-12-2015 12:08 PM

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?

Accepted Solutions

Solution

10-23-2015
10:29 AM

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

10-12-2015 04:57 PM - edited 12-01-2015 03:25 PM

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.

All Replies

Solution

10-23-2015
10:29 AM

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

10-12-2015 04:57 PM - edited 12-01-2015 03:25 PM

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
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

10-13-2015 09:17 AM

Thank you, I'll try it. Do you know of any formal SAS documentation (a book, an article) on the orienteering problem?

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

10-13-2015 10:32 AM

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
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

10-13-2015 02:09 PM

Thank you again. I really appreciate your speedy responses.

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

10-20-2015 09:57 AM

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
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

10-20-2015 10:17 AM

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
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

11-05-2015 11:49 AM

It turns out that this approach (enforcing connectivity and relaxing the distance constraint) does not scale well. Each MILP or TSP solver call is fast, but for large instances too many solver calls are required. The other approach used in the linked doc examples (enforcing the distance constraint and relaxing connectivity) scales much better, requiring relatively few solver calls even for large instances.