Re: LP - RCSP - ge resource constraint

Do I understand the example correvctly? My understanding follow.
1 You have found in the example the 'pure' shortest path.
2 You have found in the example the shortest path that consumes _at most_ 82
resources.
3 You have tried to found the shortest path that consumes _at most_ 81
resources. Not possible.

My question and problem is about finding the shortest path that consumes _at
least _ 90 resources.
Do you understand?


Look at the example:

A--------------B
| |
| |
| |
| |
| |
richard


"Erwin Kalvelagen" <erwin@xxxxxxxx> píse v diskusním príspevku
news:Vx0Nf.26807$3W5.107@xxxxxxxxxxx

I do not understand the point you are trying to make,
but here is an example in the GAMS language:


$ontext

Example of shortest path model.

Erwin Kalvelagen, april 2002

Find shortest path Tokushima to Yonago

References:
Data is takne from:
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml



$offtext

set i 'nodes' /Tokushima, Okayama, Akashi, Osaka, Kyoto, Kakogawa, Himeji,
Fukuchiyama, Wadayama, Tottori, Tsuyama, Chizu, Niimi,
Yonago/;

set s(i) 'origin' /Tokushima/;
set t(i) 'destination' /Yonago/;

alias (i,j,k);

parameter d(i,j) 'distances' /
Tokushima.Akashi 85
Tokushima.Okayama 140
Okayama.Himeji 26
Himeji.Kakogawa 12
Kakogawa.Akashi 19
Akashi.Osaka 39
Osaka.Kyoto 30
Kyoto.Fukuchiyama 74
Osaka.Fukuchiyama 105
Kakogawa.Fukuchiyama 126
Fukuchiyama.Wadayama 30
Himeji.Wadayama 67
Wadayama.Tottori 110
Himeji.Chizu 65
Himeji.Tsuyama 100
Okayama.Tsuyama 65
Okayama.Niimi 59
Tsuyama.Chizu 70
Chizu.Tottori 31
Tsuyama.Niimi 88
Tottori.Yonago 70
Niimi.Yonago 61
/;

parameter b(i) 'rhs';
b(s) = -1;
b(t) = 1;

equations
objective 'objective function'
nodebal(i) 'node balance'
;

variables
z 'total shortest distance'
x(i,j) '0-1 variable indicating path'
;

binary variable x(i,j);

*
* make the distance matrix symmetric
*
d(j,i)$d(i,j) = d(i,j);
display d;

set links(i,j) 'existing links in network';
links(i,j)$d(i,j) = yes;

objective.. z =e= sum(links, d(links)*x(links));
nodebal(k).. sum(links(i,k), x(links)) - sum(links(k,j), x(links)) =e=
b(k);

model m /all/;
solve m using rmip minimizing z;

display x.l;


parameter r(i,j) 'resource usage' /
Tokushima.Akashi 42
Tokushima.Okayama 10
Okayama.Himeji 10
Himeji.Kakogawa 14
Kakogawa.Akashi 12
Akashi.Osaka 10
Osaka.Kyoto 15
Kyoto.Fukuchiyama 19
Osaka.Fukuchiyama 10
Kakogawa.Fukuchiyama 12
Fukuchiyama.Wadayama 14
Himeji.Wadayama 15
Wadayama.Tottori 10
Himeji.Chizu 65
Himeji.Tsuyama 74
Okayama.Tsuyama 16
Okayama.Niimi 24
Tsuyama.Chizu 34
Chizu.Tottori 24
Tsuyama.Niimi 22
Tottori.Yonago 37
Niimi.Yonago 55
/;


scalar maxr 'max resource usage' /82/;

equation resource;
resource.. sum(links, r(links)*x(links)) =L= maxr;

model m2 /all/;
solve m2 using rmip minimizing z;

display x.l;

-------------------------------------------------

Pure shortest path has length 260.0000. Applying
the resource constraint causes the shortest
path to become 413. If you change resource
availability to 81, the model will become
infeasible and no proper path will be reported.


Richard Dobis wrote:
Thank you for your efford, but it is not the core of my problem.

The problem I reffer is, I think, a modeling problem, not LP solver
problem. Difference
between satisfaction (used >=) and resource (<= used ) constraint is
fundamental. Maybe RCSP
(resource consrained shortest path problem) allows be r_a <= 0 - I didn't
find any comment on this. Maybe I overlooked some properties of of
solution
method....

From strict math point of view.

The optimal solution of the formulation below of the problem SCSP
(satisfaction
constrained shortest path)

Min Sum_a c_a arc_a
S.t.:
A arc = b ---- flow conservation constraints
sum_a p_a arc_a >= P -------- p_a>=0
arc_a is binary {0,1}

shoudn't be a path. That is problem.

Very similar problem. The RCSP (resource constrained shortest path) that
is
formulated almost identically:

Min Sum_a c_a arc_a
S.t.:
A arc = b ---- flow conservation constraints
sum_a r_a arc_a <= R -------- r_a>=0
arc_a is binary {0,1}

is a path.

Well, how to formulate SCSP problem correctly? Means that optimal
solution
of LP is a path.




"W" <ogl100@xxxxxxxxx> píse v diskusním príspevku
news:1141101936.832869.119910@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Never played with LP solver; but it might use <= everywhere.

If you look this 2 LP's the only difference is in the sum_a p_a
try to use q=-p and say
sum_a q_a arc_a <= -P



Min Sum_a c_a arc_s
S.t.:
A arc = b ---- flow conservation constraints
sum_a p_a arc_a >= P
arc_a is binary {0,1}

Min Sum_a c_a arc_s
S.t.:
A arc = b ---- flow conservation constraints
sum_a t_a arc_a <= T
arc_a is binary {0,1}




"Erwin Kalvelagen" <erwin@xxxxxxxx> píse v diskusním príspevku
news:aXMMf.2166$DT.71@xxxxxxxxxxx

May be a bug in the formulation. I would first
try to see if the model solves fine without
the resource_consumption_constraint. That would
give you a pure shortest path problem. If
that works ok then add the
resource_consumption_constraint. Make sure
this constraint does not make the model infeasible!
I.e. check if the solver returns OPTIMAL or
something related. Other than that possibility,
sum(a, r(a)*binary_variable(a)) <= R
should work I think.


Richard Dobis wrote:

Hi,

I have a question about resource constraint in the resource constrained
shortest path problem in the linear programming formulation. (if you
know
about this problem skip right to the end to see my question. Thank you)

The RCSP problem in the LP formulation is:
Min cost_of_path
s.t.
flow_conservation_constraint
resource_consumption_constraint
binary_arc_variables

The graph behind is not tree! So it have cycles.

The ratio behind resource_consumption_constraint is that every arc
consumes
a portion of resource. Usually the shortest path consumes to many
resource
so we want to find a little bid longer path that consumes at most R of
resources.

The LP formulation for unique resource is:
sum_{a \in Set of Arcs} r_a binary_variable_a <= R,
where r_a is how many of the resourse is consumed using arc a.

Very often the r_a is time in the cases when minimizing total (money)
costs
of the path OR money spend in the case when minimizing jouney time.

In above examples r_a are naturally positive. Operand <= is also
natural. I
understand the reasoning why this problem has good solution (means
solution
that has no circulation).


QUESTON

My question is: how it is in case r,R are positive but operand >= is
used.
Consume at least R amount of resources.

In this case, I think, optimal solution coud be the shortest path (in
the
sense as without resource restriction) and several circulations that are
not
connected to the shortest path. Am I true?

Is there any asumtion that is not mentioned? e.g. that r_a,R MUST be
positive and <= MUST be used. (Negative r_a and R and <= are the same as
the
case I discuss)

How it is in case I mentioned? Namely, in the case r_a,R ARE positive
and
=
is used. Maybe it is completelly OK, but I cant see it.

Please if it is OK and '>=' makes no problem, please, let me know. Just
simple "You are blind, '>=' makws no problem!"

THANK YOU very much.

richard










.