% This program checks whether a depot allocation has minimal supply
% costs among all depot allocations of the same cardinality.
%
% Input predicates:
% restaurant(Name,Km), depot(Name,Km)
% Output predicates:
% altdepot(Name,Km)
%
% Author: Wolfgang Faber <wf@wfaber.com>
% License: GNU Public License, http://www.gnu.org/licenses/gpl.html

% Auxiliary predicate: All distances between restaurant locations.
distance(X,L,Y):- restaurant(R,X), restaurant(S,L), X>L,  Y = X - L.
distance(X,L,Y):- restaurant(R,X), restaurant(S,L), X<=L, Y = L - X.

% The supply distance for each restaurant for the candidate solution
% in the input. 
serves(Rname,Dist) :- restaurant(Rname,RK), depot(Dname,DK),
                      distance(RK,DK,Dist),
		      Dist = #min {Y : depot(Dname1,DK1), distance(DK1,RK,Y) }.

% Each restaurant may be an alternative depot or not.
altdepot(R,K) v naltdepot(R,K) :- restaurant(R,K).

% The number of alternative depots must be equal to the number of depots in
% the input.
:- #count{D,K: depot(D,K)} = N, #count{D1,K1: altdepot(D1,K1)} > N.
:- #count{D,K: depot(D,K)} = N, #count{D1,K1: altdepot(D1,K1)} < N.

% The supply distance for each restaurant for the alternative solution. 
altserves(Rname,Dist) :- restaurant(Rname,RK), altdepot(Dname,DK),
                  distance(RK,DK,Dist),
		  Dist = #min {Y : altdepot(Dname1,DK1), distance(DK1,RK,Y) }.

% Accept an alternative solution only if its supply costs are less
% than the supply costs for the input candidate.
:- #sum{Dist,R : serves(R,Dist)} = Cost,
   #sum{Dist1,R1 : altserves(R1,Dist1)} >= Cost.