/* SetCover *//*

/* Written in GNU MathProg by Philippe Gambette */

param nbelements, integer, >= 3;
/* number of elements */

param nbsets, integer, >= 3;
/* number of sets */

set elements := 1..nbelements;
/* set of elements */

set sets := 1..nbsets;
/* set of sets */

set E, within elements cross sets;
/* set of arcs */

param cost{j in sets};
/* cost of a set */

param c{(i,j) in E};
/* cost of an edge */

var x{j in sets}, binary;
/* x[j] = 1 means set i is selected */

minimize total: sum {j in sets} cost[j] * x[j];
/* the objective is to make the set cover cost as small as possible */

s.t. cover{i in elements}: sum{(i,j) in E} x[j] >= 1;
/* each elements is covered by a set of the solution */

solve;

printf "Optimal set cover has cost %d",
   sum {j in sets} cost[j] * x[j];
printf " with %d elements\n",
   sum {i in sets} x[i];

printf("with sets:\n");

printf{i in sets: x[i]} "      %3d\n",
   i;
/*printf{i in sets: x[i]} "      %3d       %8g\n",
   i, c[i,j];*/

data;


param nbelements := 9;
param nbsets := 18;

param : E : c:=
    1  1  1
    2  2  1    
    1  3  1
    2  3  1
    3  3  1
    3  4  1
    3  5  1
    4  5  1
    3  6  1
    6  6  1
    5  7  1
    4  8  1
    5  8  1
    6  8  1
    4  9  1
    8  9  1
    5  10 1
    7  10 1
    6  11 1
    9  11 1
    7  12 1
    8  12 1
    8  13 1
    7  14 1
    9  14 1
    6  15 1
    7  15 1
    8  15 1
    9  15 1
    7  16 1
    8  16 1
    9  16 1
    8  17 1
    9  17 1
    9  18 1

;

param cost [1] 645 [2] 645 [3] 1920 [4] 1195 [5] 2395 [6] 995 [7] 995 [8] 1445 [9] 995 [10] 995 [11] 2245 [12] 645 [13] 995 [14] 495 [15] 1795 [16] 1095 [17] 699 [18] 726 
;

end;