# caractéristiques de la grille
set I;
set J;
# caractéristiques de la grille
param d;
# degré de redondance de couverture
param p;
# degré de redondance de couverture
param q;
# Obstacle(i,j), entrée si obstacle exist
set O, dimen 2;

# 1 si on installe un capteurs en le noeud (i,j)
var x{I,J}, binary;

minimize nombre_capteurs :
  sum{i in I, j in J} x[i,j];

# Couverture de chaque noeud par p capteurs
s.t. c1{i in I, j in J} :
  sum{k in I, l in J : (k-i)^2 + (l-j)^2 <= d^2} x[k,l] >= p;

# q-connectivités des capteurs
s.t. c2{i in I, j in J} :
  sum{k in I, l in J : (k-i)^2 + (l-j)^2 <= d^2} x[k,l] >= (q + 1) * x[i,j];

# Présence d'obstacle
s.t. c3{(i,j) in O} :
  x[i,j] = 0;

solve;

# présentation des résultats
printf "     |";
printf{i in I} " %3d |", i;
printf "\n";
printf "-----+";
printf{i in I} "-----+", i;
printf "\n";
for {j in J} {
  printf " %3d |", j;
  printf{i in I} "  %1s  |",
    if (x[i,j] > .5) then "X"
    else (
      if ((i,j) in O) then "O"
      else " ");
  printf "\n";
  }

data;

set I := 1 2 3 4 5 6 7 8;
set J := 1 2 3 4 5 6 7 8;
set O :=
  3 4
  5 7
  2 4;
param d := 3;
param p := 8;
param q := 4;

end;