How can I implement these 2 additional constraint in this AMPL shortest path problem?

173 views Asked by At

This is the problem

So given this, If I want to Formulate an ILP model to determine the least costly route in case there are the following additional constraints:

-if arc (1,4) is used, then also arc (4,6) must be used; -on the other hand, if arc (1,4) is not used, then the route must pass through node 9.

How can I implement these new 2 constraints in the ILP model?

I figured out how to implement an ILP Model through AMPL not considering these 2 additional constraints but limiting to minimizing the route from Detroit to Charleston in this way: these are the 2 files .mod and .dat necessary to do so. File .mod here

#model
set Nodes;
set Origins within (Nodes);
set Destinations within (Nodes);
set Link within (Nodes cross Nodes);

param Costs {Link};
param Balancies {Nodes};

var ConstrCost{Link} >=0;

minimize Total_Cost: sum{(i,j) in Link} Costs[i,j]*ConstrCost[i,j];

subject to StartingBalance {i in Origins}:-sum {(i,k) in Link} ConstrCost[i,k] == Balancies [i];
subject to FinalBalance {i in Destinations}:sum {(j,i) in Link} ConstrCost[j,i]-sum {(i,k) in Link} ConstrCost[i,k] == Balancies[i];            

File.dat here.

data;
set Nodes := Detroit Due Tre Quattro Cinque Sei Sette Otto Nove Dieci Undici Charleston;
set Origins:= Detroit;
set Destinations:= Due Tre Quattro Cinque Sei Sette Otto Nove Dieci Undici Charleston;
set Link:=(Detroit,Due)
(Detroit,Tre)
(Detroit,Quattro)
(Due, Cinque)
(Due, Sei)
(Tre, Sei)
(Quattro, Sei)
(Quattro, Sette)
(Quattro, Nove)
(Cinque, Sei)
(Cinque, Otto)
(Cinque, Nove)
(Sei, Nove)
(Sette, Nove)
(Sette, Dieci)
(Otto, Undici)
(Nove, Undici)
(Nove, Charleston)
(Dieci, Undici)
(Dieci, Charleston)
(Undici, Charleston);

param Costs:=
Detroit,Due 1
Detroit,Tre 3
Detroit,Quattro 2
Due, Cinque 4
Due, Sei 3
Tre, Sei 2
Quattro, Sei 2
Quattro, Sette 3
Quattro, Nove 4 
Cinque, Sei 1
Cinque, Otto 3
Cinque, Nove 3
Sei, Nove 2
Sette, Nove 2
Sette, Dieci 3
Otto, Undici 2
Nove, Undici 1
Nove, Charleston 2
Dieci, Undici 3
Dieci, Charleston 5
Undici, Charleston 3;

param Balancies :=
Detroit -1
Due 0
Tre 0
Quattro 0
Cinque 0
Sei 0
Sette 0
Otto 0
Nove 0
Dieci 0
Undici 0
Charleston 1;

Now, given these 2 files, how can I implement the 2 additional constraints?

1

There are 1 answers

0
ab.fe On

Since your variables are : ConstrCost

  1. constraint 1 :

if arc (1,4) is used, this means ConstrCost[1,4]>0, then also arc (4,6) must be used i.e ConstrCost[4,6]>0

subject to {if ConstrCost[1,4]>0}:
   ConstrCost[4,6]>0;
  1. Constraint 2: if arc (1,4) is not used(i.e ConstrCost[1,4]=0), then the route must pass through node 9, this means node 9 must be used at least once as an Origin or as Destination :
subject to {if ConstrCost[1,4]==0}:
   sum{i in Origins} ConstrCost[i,9]+sum{j in Destinations} ConstrCost[9,j]>0

Take into consideration that your model won't recognize (1,4), so you should replace by Origins and destinations name...