/*

  Set covering problem in Picat.

  Example 9.1-2, page 354ff, from Taha "Operations Research - An Introduction"
  Minimize the number of security telephones in street corners on a campus.

  AMPL model: http://taha.ineg.uark.edu/setcover.txt


  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

%
% First find the optimal value (MinVal) i.e. the number of telephones
% placed. Then find all the solutions with that value.
%
go =>
        writef("Find the optimal solution:\n"),
        corners(N, Corners),
        set_covering2(N, Corners, MinVal, _X),

        writef("\nFinding all optimal solutions with MinVal %d:\n", MinVal),
        L = findall(X, $set_covering2(N, Corners, MinVal, X)),
        Len = length(L),
        writeln(L),
        writef("It was %d solutions\n", Len).


set_covering2(N, Corners, MinVal, X) =>
      
        % where to place the telephones
        X = new_list(N),
        X :: 0..1,
        
        % All streets must be covered
        foreach(I in 1..Corners.length) 
           X[Corners[I,1]] + X[Corners[I,2]] #>= 1
        end,


        % objective: minimize the number of telephones
        MinVal #= sum(X),

        % Either search for all solutions (with the minimum value) or
        % search for the optimal value.
        if ground(MinVal) then
            solve(X)
        else
            solve([$min(MinVal)], X)
        end,

        writeln(minVal=MinVal),
        writeln(x=X).


% corners of each street
%
% corners(NumberOfStreets, Corners)
%
corners(N, Corners) => 
        N = 8,
        Corners =
            {{1,2},
              {2,3},
              {4,5},
              {7,8},
              {6,7},
              {2,6},
              {1,6},
              {4,7},
              {2,4},
              {5,8},
              {3,5}}.