%
% MiniZinc implementation of the example of Set Covering Deployment at
% 
% http://mathworld.wolfram.com/SetCoveringDeployment.html
%
% This Minizinc program was written by Hakan Kjellerstrand, hakank@bonetmail.com,
% and is commented in the (swedish) blog post
% Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc
% http://www.hakank.org/webblogg/archives/001209.html
%
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

int: n;                                           % number of countries
var int: c_armies = sum(i in 1..n) (X[i] + Y[i]); % number of armies (objective to minimize)

array[1..n, 1..n] of int: matrix;                 % the incidence matrix

array[1..n] of var 0..1: X;                       % the first army
array[1..n] of var 0..1: Y;                       % the second (reserve) army


solve minimize c_armies;
% use this when constraint 3 is activated: show all optimal solutions
% solve satisfy; 

%
% Constraints
%

% Constraint 1: There is always an army in a city (+ maybe a backup)
%               Or rather: Is there a backup, there must be an an army
constraint 
           forall(i in 1..n) (
              X[i] >= Y[i]
           )
;

% Constraint 2: There should always be an backup army near every city
constraint 
           forall(i in 1..n) (
                     (X[i] + sum(j in 1..n where matrix[i,j] = 1) (Y[j]))  >= 1
           )
;

% Constraint 3 for showing all the solutions. 
% After a 
%   solve minimize 
% we know that the required number of armies is 4. 
% Now we could use 
%    solve satisfy 
% to see every solution.
% constraint 
%            sum(i in 1..n) (X[i] + Y[i]) <= 4
% ;


% data
n = 8;

matrix = 
array2d(1..n, 1..n,
[ 0,   1,   0,   1,   0,   0,   1,   1,
  1,   0,   0,   1,   0,   0,   0,   0,
  0,   0,   0,   0,   1,   1,   0,   0,
  1,   1,   0,   0,   0,   0,   1,   0,
  0,   0,   1,   0,   0,   1,   1,   0,
  0,   0,   1,   0,   1,   0,   1,   1,
  1,   0,   0,   1,   1,   1,   0,   1,
  1,   0,   0,   0,   0,   1,   1,   0
])
;


output [
       "[alexandria, asia_minor, britain, byzantium, gaul, iberia, rome, tunis]","\n",
       "X: ", show(X),"\n",
       "Y: ", show(Y),"\n",
       "c_armies: ", show(c_armies), "\n"
]