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**.
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 08-08-2022 02:22 PM
(745 views)

Greetings!

I am faced with a slightly modified TSP problem as below:

There are 4 nodes with directional values:

FRIDX | TOIDX | INC |

1 | 2 | -0.23548 |

1 | 3 | -0.14027 |

1 | 4 | -0.22685 |

2 | 1 | 0.014942 |

2 | 3 | -0.02719 |

2 | 4 | -0.11378 |

3 | 1 | 0.076665 |

3 | 2 | -0.06068 |

3 | 4 | -0.05206 |

4 | 1 | 0.059285 |

4 | 2 | -0.07806 |

4 | 3 | 0.017148 |

However INC above is not the cost in a TSP problem. TO calculate the costs, here is another table:

Trip # | HIST_INC |

1 | -0.072240154 |

2 | -0.075171085 |

3 | -0.077492213 |

Where trip # represent the subtrip number traveling to all nodes above without return. That is, 4 -->2 --> 1 --> 3 requires 3 subtrips.

HIST_INC is a historical value for INC I want to align with by defining the cost as:

cost = sum (sq(INC - HIST)) for all 3 trips (across 4 nodes).

Therefore, the costs are not only determined by the starting and ending nodes and their directions, but also by the order of each subtrip within the entire iteration acorss all nodes. For example, the cost of subtrip from 4 to 1 could take any of the three values, depending on the order of the subtrip within the enture trip (without return):

sq(0.059285 + 0.072240154)

sq(0.059285 + 0.075171085)

sq(0.059285 + 0.077492213)

I hope my explanation is clear; if not I'd be glad to further clarify. I looked up PROC OPTNETWORK used it for a standard TSP, but no luck with this one.

Thanks in advance!

Bo

1 ACCEPTED SOLUTION

Accepted Solutions

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

It looks like you are using an older version that does not support comparison of tuples. I recommend upgrading, but until then here are three workarounds:

` = (if <i,t> in {<SOURCE,0>} then 1 else if <i,t> in {<SINK,n+1>} then -1 else 0);`

= (if i = SOURCE and t = 0 then 1 else if i = SINK and t = n+1 then -1 else 0);

```
= (if i = SOURCE then 1 else if i = SINK then -1 else 0);
```

6 REPLIES 6

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

The standard TSP model does not allow time-dependent costs. Instead, you can solve your problem as a side-constrained shortest path problem in a directed acyclic network with 18 nodes:

- (0,0): this is a dummy source node
- (i,t) for i in 1..4 and t in 1..4
- (5,5): this is a dummy sink node

The arcs are from (i,t) to (j,t+1), where i in 0..4, j in 1..5, and t in 0..4, and you can compute the arc costs according to your formula.

The decision variables are UseArc[i,j,t], and you need a flow balance constraint for each node, as well as a side constraint sum {<i,(j),t> in ARCS} UseArc[i,j,t] >= 1 for j in 1..4.

This approach is a simpler version of the one illustrated in the "Network Formulation" section of https://support.sas.com/resources/papers/proceedings14/SAS101-2014.pdf.

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

Thanks for your quick reply, Rob!

Could you help me with the syntax? I am a beginner with Proc optmodel and here is what I have so far.

PROC OPTMODEL;

SET TS = 1..4;

SET IDX = 1..4;

NUM SOURCE = 0;

NUM SINK = 1 + MAX {I in IDX} I;

SET NODES = IDX UNION {SOURCE, SINK};

SET <NUM, NUM> ARCS INIT {};

NUM INCS {IDX, IDX};

NUM INCAVG {TS};

READ DATA DYINC_M INTO [I=FRIDX]{J IN IDX} <INCS[I,J]=COL('INC'||J)>;

READ DATA HISINCAVG_M INTO [DYIDX] INCAVG=INC;

VAR USEARC {ARCS} BINARY;

NUM COST {I IN IDX, J IN IDX, T IN TS} = (INCS[I,J] - INCAVG[T])**2;

MIN TOTALCOST = SUM{I IN IDX, J IN IDX} COST[I,J]*USEARC[I,J];

...

QUIT;

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

Here are the requested modifications to your code, together with optional PUT, PRINT, and EXPAND statements to help see what is going on:

```
data DYINC_M;
input FRIDX TOIDX INC;
datalines;
1 2 -0.23548
1 3 -0.14027
1 4 -0.22685
2 1 0.014942
2 3 -0.02719
2 4 -0.11378
3 1 0.076665
3 2 -0.06068
3 4 -0.05206
4 1 0.059285
4 2 -0.07806
4 3 0.017148
;
data HISINCAVG_M;
input DYIDX INC;
datalines;
1 -0.072240154
2 -0.075171085
3 -0.077492213
;
PROC OPTMODEL;
num n = 4;
SET TS = 1..n;
SET IDX = 1..n;
NUM SOURCE = 0;
NUM SINK = 1 + MAX {I in IDX} I;
SET NODES = (IDX cross TS) UNION {<SOURCE,0>, <SINK,n+1>};
SET ARCS =
setof {i in IDX} <SOURCE,i,0>
union
setof {i in IDX, j in IDX diff {i}, t in TS} <i,j,t>
union
setof {i in IDX} <i,SINK,n>
;
put NODES=;
put ARCS=;
NUM INCS {IDX, IDX};
NUM INCAVG {TS};
READ DATA DYINC_M INTO [FRIDX TOIDX] INCS=INC;
print INCS;
READ DATA HISINCAVG_M INTO [DYIDX] INCAVG=INC;
print INCAVG;
VAR USEARC {ARCS} BINARY;
NUM COST {<i,j,t> in ARCS} = if t in 1..n-1 then (INCS[I,J] - INCAVG[T])**2;
print cost;
MIN TOTALCOST = SUM{<i,j,t> in ARCS} COST[i,j,t]*USEARC[i,j,t];
con FlowBalance {<i,t> in NODES}:
sum {<(i),j,(t)> in ARCS} UseArc[i,j,t] - sum {<j,(i),(t)-1> in ARCS} UseArc[j,i,t-1]
= (if <i,t> = <SOURCE,0> then 1 else if <i,t> = <SINK,n+1> then -1 else 0);
con VisitOnce {j in IDX}:
sum {<i,(j),t> in ARCS} UseArc[i,j,t] = 1;
expand;
solve;
print {<i,j,t> in ARCS: UseArc[i,j,t].sol > 0.5} cost;
QUIT;
```

The resulting optimal solution uses the following arcs:

[1] | [2] | [3] | COST |
---|---|---|---|

0 | 1 | 0 | 0.00000000 |

1 | 3 | 1 | 0.00462806 |

2 | 5 | 4 | 0.00000000 |

3 | 4 | 2 | 0.00053412 |

4 | 2 | 3 | 0.00000032 |

The corresponding path is 1->3->4->2.

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

Thanks, Rob! I did encounter one error, however:

57 con FlowBalance {<i,t> in NODES}:

58 sum {<(i),j,(t)> in ARCS} UseArc[i,j,t] - sum {<j,(i),(t)-1> in ARCS} UseArc[j,i,t-1]

59 = (if <i,t> = <SOURCE,0> then 1 else if <i,t> = <SINK,n+1> then -1 else 0);

_

22

76

ERROR 22-322: Syntax error, expecting one of the following: IN, NOT, ~.

ERROR 76-322: Syntax error, statement will be ignored.

Any ideas?

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

It looks like you are using an older version that does not support comparison of tuples. I recommend upgrading, but until then here are three workarounds:

` = (if <i,t> in {<SOURCE,0>} then 1 else if <i,t> in {<SINK,n+1>} then -1 else 0);`

= (if i = SOURCE and t = 0 then 1 else if i = SINK and t = n+1 then -1 else 0);

```
= (if i = SOURCE then 1 else if i = SINK then -1 else 0);
```

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

Thanks, Rob! It works like a charm!

My actual usage has i=0..30, j=1-30, and t=1..30. With your code it takes around 15 seconds to solve.

Build your skills. Make connections. Enjoy creative freedom. Maybe change the world. **Registration is now open through August 30th**. Visit the SAS Hackathon homepage.

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.