1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | % bibd.mzn % vim: ft=zinc ts=4 sw=4 et tw=0 % Ralph Becket <rafe@csse.unimelb.edu.au> % Tue Oct 23 11:28:06 EST 2007 % % Balanced incomplete block designs. See the following: % http://www.dcs.st-and.ac.uk/~ianm/CSPLib/prob/prob028/spec.html % % % % A BIBD (v, b, r, k, lambda) problem is to find a binary matrix of v rows % of b columns such that each row sums to r, each column sums to k, and % the dot product beween any pair of distinct rows is lambda. include "lex_lesseq.mzn" ; int : v; int : k; int : lambda; int : b = (lambda * v * (v - 1)) div (k * (k - 1)); int : r = (lambda * (v - 1)) div (k - 1); set of int : rows = 1..v; set of int : cols = 1..b; array [rows, cols] of var bool : m; % Every row must sum to r. % constraint forall (i in rows) ( sum (j in cols) ( bool2int (m[i, j])) = r); % Every column must sum to k. % constraint forall (j in cols) ( sum (i in rows) ( bool2int (m[i, j])) = k); % The dot product of every pair of distinct rows must be lambda. % constraint forall (i_a, i_b in rows where i_a < i_b) ( sum (j in cols) ( bool2int (m[i_a, j] /\ m[i_b, j])) = lambda ); % Break row symmetry in the incidence matrix. % constraint forall (i in rows diff { max (rows)})( lex_lesseq([m[i, j] | j in cols], [m[i+1, j] | j in cols]) ); % Break column symmetry in the incidence matrix. % constraint forall (j in cols diff { max (cols)})( lex_lesseq([m[i, j] | i in rows], [m[i, j+1] | i in rows]) ); solve :: bool_search([m[i, j] | i in rows, j in cols], input_order, indomain_min, complete) satisfy ; output [ "bibd: (v = " , show (v), ", b = " , show (b), ", r = " , show (r), ", k = " , show (k), ", lambda = " , show (lambda), ")\n\n" ] ++ [ ( if j > b then "\n" else show ( bool2int (m[i, j])) endif ) | i in rows, j in 1..(b + 1) ]; %----------------------------------------------------------------------------% %----------------------------------------------------------------------------% |