Selecting the path out of the set of paths

[Anna]

Hello,

my problem is following:

set V; # set of nodes;
set arc within {i in V, j in V: i<>j}; # set of arcs between
nodes;
set P; # set of paths;
set E{s in S} within arc; # sequence of arcs in each paths;
set N{s in S} within V; # set of nodes, which belong to the path s;


set D; # set of demands for transit from i to j;

param orig{D} within V; # origin of a demand;
param dest{D} within V; # destination of a demand;
set Link{d in D} := {orig[d]} cross {dest[d]};

can I search for all paths that satisfy demand d with origin and
destination (orig[d], dest[d])?? or if the path goes through i=orig[d]
and j=dest[d]?? And then select these paths and create a set of
possible paths for each demand d?

data.dat
## Network ##
set V := 1 2 3 4;
set S := S1 S2 S3;

## Paths ##
set E[S1]:= (2,3) (3,4) (4,1);
set E[S2]:= (2,1);
set E[S3]:= (2,3) (3,4);

set N[S1]:= 2 3 4 1;
set N[S2]:= 2 1;
set N[S3]:= 2 3 4;

set arc :=
(*,*): 1 2 3 4 :=
1 - - - -
2 + - + -
3 - - - +
4 + - - -;

## Demand ##
set D := d1 d2 d3 d4 d5;

param orig[*]:=
d1 2
d2 2
d3 3
d4 3
d5 4;

param dest[*]:=
d1 1
d2 3
d3 1
d4 4
d5 1;


I will appreciate any advice or suggestion!!!!
Thank you in advance!

Anna

[Paul]

First, an observation:  you do not need semicolons at the end of comments.

Second, should "set P;" be "set S;"?  You never declare S in the model portion, and you never use P after declaring it.

Third, if you want E and N to contain arcs and nodes in the order they appear on a path, you probably should declare them to be ordered sets.  It may or may not matter for what you are doing.

If I understand your question correctly,

display {d in D, s in S : (orig[d] in N[s]) && (dest[d] in N[s])};

will display every pair of a demand d and a path s where the origin and destination appear somewhere along the path.  If you specifically need to isolate paths that begin at orig[d] and end at dest[d], then you need to declare N to be ordered, in which case

display {d in D, s in S : (orig[d] == first(N[s])) && (dest[d] == last(N[s]))};

should work.  Finally (?), if you want to find paths that pass through orig[d] and dest[d] in that order, but do not necessarily begin at orig[d] or end at dest[d], then (with N ordered) you can try

display {d in D, s in S : (orig[d] in N[s]) && (dest[d] in N[s]) && (ord(orig[d], N[s]) < ord(dest[d], N[s]))};

Paul

[Robert Fourer]

Typically a shortest-path formulation uses zero-one variables -- see for
example www.ampl.com/BOOK/EXAMPLES/EXAMPLES2/netshort.mod. So you might
want to look at this talk:

www.ampl.com/MEETINGS/TALKS/2011_08_Zurich_TC22.pdf

It shows two different ways of finding multiple solutions to a MIP involving
zero-one variables -- not for the shortest-path model, but readily
adaptable. For a small problem you ought to be able to use one of these
approaches to find all solutions.

Bob Fourer
4...@ampl.com

> -----Original Message-----
> From: am...@googlegroups.com [mailto:am...@googlegroups.com]
> On Behalf Of Anna
> Sent: Thursday, February 09, 2012 10:32 AM
> To: AMPL Modeling Language
> Subject: [AMPL 5443] Selecting the path out of the set of paths
>
> Hello,
>
> my problem is following:
>
> set V; # set of nodes;
> set arc within {i in V, j in V: i<>j}; # set of arcs between
nodes;
> set P; # set of paths;
> set E{s in S} within arc; # sequence of arcs in each paths;
> set N{s in S} within V; # set of nodes, which belong to the path s;
>
>
> set D; # set of demands for transit from i to j;
>
> param orig{D} within V; # origin of a demand;
> param dest{D} within V; # destination of a demand;
> set Link{d in D} := {orig[d]} cross {dest[d]};
>
> can I search for all paths that satisfy demand d with origin and
> destination (orig[d], dest[d])?? or if the path goes through i=orig[d]
> and j=dest[d]?? And then select these paths and create a set of
> possible paths for each demand d?
>

> ...

[Anna]

Thank you very much for your advice!

I added the shortest-path problem to find the min cost path. So now I
select all possible paths for each demand as Paul suggested and then
search for the "shortest" among them. Otherwise the model gives the
combinations of arcs from different defined paths. However I cannot
use in my shortest path the combination of links which belong to
different paths. I hope my explanations make sense.

Afterward I formulate the min cost flow problem as a path formulation.
After adding this problem I get a wrong result. I get the flow and the
paths for the flow but the model doesn't choose the min cost result.

I cannot understand what is wrong or if I can combine 2 problems in 1.
Maybe there must be some transition between the main problem (defining
the flow on the path) and the subproblem (shortest-path problem) but I
simply don't know this.

So here is the written code. I would appreciate greatly if you could
have a look and give any advice or suggestion!
-----
## NETWORK ##

set V; # set of nodes

set arcs within {i in V, j in V: i<>j}; # set of arcs between
nodes

## PATHES ##
set S; # set of paths
set E{s in S} within arcs; # sequence of arcs in each paths
set N{s in S} within V ordered; # set of nodes, which belong to the
path s in S

## DEMAND ##

set D; # set of demands for transit from i to j

param orig{D} within V; # origin of demand d
param dest{D} within V; # destination of demand d

set Link{d in D} := {orig[d]} cross {dest[d]};

param n{d in D, {orig[d]}, {dest[d]}}; # number of units to be
transfered from i to j


## SET OF POSSIBLE PATHES FOR EACH DEMAND ##
set P{d in D} := {s in S: (orig[d] in N[s]) &&

(dest[d] in N[s]) &&
(ord(orig[d], N[s]) < ord(dest[d], N[s]))};

### TRANSPORTATION ###
param cost{S} >= 0; # cost per time unit
param time{arcs} >= 0;


##------------------------------------------
## SHORTEST PATH PROBLEM
##------------------------------------------

var Use {d in D, s in P[d], (i,j) in E[s]} binary; # 1 if (i,j) in
min cost path

minimize Total_Cost_Path:
sum {d in D, s in P[d], (i,j) in E[s]}
time[i,j]*cost[s]*Use[d,s,i,j];

subject to Start{i in V, d in D: i=orig[d]}:
sum {j in V, s in P[d]: (i,j) in E[s]} Use[d,s,i,j] = 1;

subject to Trans {i in V, d in D: i<>orig[d] and i<>dest[d]}:
sum {j in V, s in P[d]: (i,j) in E[s]} Use[d,s,i,j] - sum{j in V, s
in P[d]: (j,i) in E[s]} Use[d,s,j,i] = 0;

subject to End{i in V, d in D: i=dest[d]}:
sum {j in V, s in P[d]: (j,i) in E[s]} Use[d,s,j,i] = 1;


##-----------------------------------------------------------
## PATH FLOW FORMULATION ##
##-----------------------------------------------------------

var f{d in D, s in P[d]} >= 0, integer; # flow of units of demand d
in the one of the possible pathes for this demand

### OBJECTIVE ###
minimize Total_Cost_Flow:
sum {d in D, s in P[d], (i,j) in E[s]}
cost[s]*time[i,j]*Use[d,s,i,j]*f[d,s];

### CONSTRAINTS ###

subject to DemandSatisfaction {d in D, (i,j) in Link[d]}:
sum{s in P[d]} f[d,s] = n[d,i,j];

data;

## Network ##
set V := 1 2 3 4;
set S := S1 S2 S3;
## Paths ##
set E[S1]:= (2,3) (3,4) (4,1);
set E[S2]:= (2,1);
set E[S3]:= (2,3) (3,4);

set N[S1]:= 2 3 4 1;
set N[S2]:= 2 1;
set N[S3]:= 2 3 4;

set arcs :=

(*,*): 1 2 3 4 :=
1 - - - -
2 + - + -
3 - - - +
4 + - - -;

## Demand ##
set D := d1 d2 d3 d4 d5;

param orig[*]:=
d1 2
d2 2
d3 3
d4 3
d5 4;

param dest[*]:=
d1 1
d2 3
d3 1
d4 4
d5 1;

param n:=
[d1,2,1] 5
[d2,2,3] 5
[d3,3,1] 15
[d4,3,4] 15
[d5,4,1] 10;

## Transportation ##
param cost[*]:=
[S1] 2
[S2] 100
[S3] 1;

param time :=
[*,*]: 1 2 3 4 :=
1 . . . .
2 1 . 1 .
3 . . . 1
4 1 . . .;

Thank you in advance and best regards!!!
Anna

[Robert Fourer]

Did you just read all of these statements into AMPL and then invoke "solve"?
Then the solver would only minimize the first objective function; the second
would be ignored.

Perhaps you want to solve the first problem with the first objective, fix
the Use variables at their optimal values, and then solve the second problem
with the second objective. Then you need to give some AMPL commands to
define two separate problems and do two separate solves, such as these:

problem ShortestPath: Use, Total_Cost_Path, Start, Trans, End;
problem PathFlow: f, Total_Cost_Flow, DemandSatisfaction;

solve ShortestPath;
solve PathFlow;

In general you will need a little script of this sort to define any scheme
that involves more than one optimization.

Bob Fourer
4...@ampl.com

> -----Original Message-----
> From: am...@googlegroups.com [mailto:am...@googlegroups.com]
> On Behalf Of Anna
> Sent: Monday, February 13, 2012 11:35 AM
> To: AMPL Modeling Language