1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   2 %%%%%%% VALVES LOCATION OPTIMIZATION %%%%%%%
   3 %%%%%%% FO: MAX MIN SATISFIED DEM.   %%%%%%%
   4 %%%%%%%   TYPE: PIPE REACHABILITY    %%%%%%%
   5 %%%%%%%   ANDREA PEANO 10/10/2012    %%%%%%%
   6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   7 
   8 		%just some tools
   9 		%Symmetric pipe
  10 symm_pipe(A,B):- pipe(A,B).
  11 symm_pipe(B,A):- pipe(A,B).
  12 		%We need a lexicographic order (there may be more than one worst isolation cases)
  13 less_ico(pipe(A,B), pipe(C,D)):- pipe(A,B), pipe(C,D), A<C.
  14 less_ico(pipe(A,B), pipe(C,D)):- pipe(A,B), pipe(C,D), A = C, B<D.
  15 
  16 %Adjacency of pipes (common junction and unshared junctions)
  17 %adj(pipe(X,Y), pipe(W,Z), COM, U1, U2) :- symm_pipe(COM,U1), symm_pipe(COM,U2), U1!=U2, not tank(COM),
  18 %				pipe(X,Y), pipe(W,Z), 
  19 %                                2 {COM=W, COM=Z, COM=X, COM=Y} 2,
  20 %				1 {U1=W, U1=Z, U1=X, U1=Y} 1,
  21 %				1 {U2=W, U2=Z, U2=X, U2=Y} 1.
  22 adj(pipe(X,Y), pipe(W,Z), COM, U1, U2) :- symm_pipe(COM,U1), symm_pipe(COM,U2), U1!=U2, not tank(COM),
  23 				pipe(X,Y), pipe(W,Z), 
  24                                 2 = #count {COM : COM=W; COM : COM=Z; COM : COM=X; COM : COM=Y},
  25 				1 = #count {U1 : U1=W; U1 : U1=Z; U1 : U1=X; U1 : U1=Y},
  26 				1 = #count {U2 : U2=W; U2 : U2=Z; U2 : U2=X; U2 : U2=Y}.
  27 
  28 
  29 
  30 		%
  31 		%There are some valves that are closed to isolate the broken pipe
  32 1 <= { closed_valve(v(X,Y), broken(A,B)) : symm_pipe(X,Y) } <= Nv :- pipe(A,B), valves_number(Nv).
  33 
  34 		%
  35 		%If a valve is closed for some pipes, then it must be installed!!
  36 valve(A,B) :- closed_valve(v(A,B), _).
  37 
  38 		%
  39 		%There should always be installed valves near the tanks
  40 valve(A,B) :- symm_pipe(A,B), tank(A).
  41 
  42 		%
  43 		%Valves must be at most Nv
  44 :- valves_number(Nv), not Nv = #count{ X,Y : valve(X,Y) , pipe(X,Y); Y,X : valve(Y,X) , pipe(X,Y)}.
  45 
  46 		%
  47 		%At most X valves per pipe must be allowed (either 1 or 2)
  48 :- valves_per_pipe(1), pipe(A,B), valve(A,B), valve(B,A).
  49 
  50 		%
  51 		%some symmetry breaking on valves
  52 :- junction(X), not tank(X), symm_pipe(X,A), symm_pipe(X,B),
  53 		2 = #count{ X,Y : symm_pipe(X,Y) }, A>B, valve(X,A).
  54 
  55 		%
  56 		%A pipe adjacent to the tank is reached, when a generic pipe is broken iff there is no valve between them.
  57 reached(pipe(A,B), broken(X,Y)):- tank(A), pipe(X,Y), pipe(A,B), not closed_valve(v(A,B), broken(X,Y)).
  58 reached(pipe(A,B), broken(X,Y)):- tank(B), pipe(X,Y), pipe(A,B), not closed_valve(v(B,A), broken(X,Y)).
  59 
  60 		%
  61 		%Can we recursively reach any tank??
  62 reached(pipe(A,B), broken(X,Y)) :- adj(pipe(A,B), pipe(C,D), COM, U1, U2), %COM is not a tank! 
  63 				not closed_valve(v(COM,U1), broken(X,Y)),
  64 				not closed_valve(v(COM,U2), broken(X,Y)),
  65 				reached(pipe(C,D), broken(X,Y)).
  66 
  67 		%
  68 		%The broken pipe must be unreachable!
  69 :- pipe(A,B), reached(pipe(A,B), broken(A,B)).
  70 
  71 		%
  72 		% Pair-wise comparisons between delivered demand pipe isolation cases
  73 %lower(pipe(X,Y), pipe(W,Z)) :- pipe(X,Y), pipe(W,Z),
  74 %		#sum [ 	reached(pipe(A,B), broken(X,Y))=Dn: dem(A,B,Dn),
  75 %			reached(pipe(C,D), broken(W,Z))=-Dm: dem(C,D,Dm) ] 0.
  76 lower(pipe(X,Y), pipe(W,Z)) :- pipe(X,Y), pipe(W,Z),
  77 		S1 = #sum { Dn,A,B,X,Y : reached(pipe(A,B), broken(X,Y)), dem(A,B,Dn) },
  78                 S2 = #sum { Dm,C,D,W,Z : reached(pipe(C,D), broken(W,Z)), dem(C,D,Dm) }, S1 - S2 = 0.
  79 
  80 		%
  81 		%Then the lower are...
  82 lower_lexico(pipe(X,Y), pipe(W,Z)) :- pipe(X,Y), pipe(W,Z),
  83 				lower(pipe(X,Y), pipe(W,Z)), not lower(pipe(W,Z), pipe(X,Y)).
  84 lower_lexico(pipe(X,Y), pipe(X,Y)) :- pipe(X,Y),
  85 				lower(pipe(X,Y), pipe(X,Y)).
  86 lower_lexico(pipe(X,Y), pipe(W,Z)) :- pipe(X,Y), pipe(W,Z), % with the same delivered demand
  87 				lower(pipe(X,Y), pipe(W,Z)), lower(pipe(W,Z),pipe(X,Y)),
  88 				less_ico(pipe(X,Y), pipe(W,Z)).
  89 
  90 		%
  91 		%And the worst isolation case is the one for which all lower_lexico are true
  92 %worst(pipe(X,Y)) :- pipe(X,Y), lower_lexico(pipe(X,Y),pipe(W,Z)) : pipe(W,Z).
  93 worst(pipe(X,Y)) :- pipe(X,Y), C = #count { W,Z : pipe(W,Z) }, 
  94                                D = #count{ X,Y,W,Z : lower_lexico(pipe(X,Y),pipe(W,Z)) , pipe(W,Z)}, C = D.
  95 
  96 
  97 worst_deliv_dem(pipe(A,B), D) :- dem(A,B,D), pipe(X,Y),
  98 		reached(pipe(A,B), broken(X,Y)), worst(pipe(X,Y)).
  99 
 100 		%
 101 		%Worst isolation case' delivered demand maximization
 102 
 103 :~ pipe(A,B), not worst_deliv_dem(pipe(A,B),D). [D]
 104 %#maximize [ worst_deliv_dem(pipe(A,B), D)=D : pipe(A,B) ].
 105 
 106 %#hide.
 107 %#show valve/2.
 108 %#show worst_deliv_dem/2.