Outils pour l'Analyse Dynamique et la mise au Point de
Programmes avec Contraintes

## Balanced Incomplete Block Design (BIBD)

Problem description (see CSPLib : prob28) :

Balanced Incomplete Block Design (BIBD) generation is a standard combinatorial problem from design theory, originally used in the design of statistical experiments but since finding other applications such as cryptography. It is a special case of Block Design, which also includes Latin Square problems.

BIBD generation is described in most standard textbooks on combinatorics. A BIBD is defined as an arrangement of v distinct objects into b blocks such that each block contains exactly k distinct objects, each object occurs in exactly r different blocks, and every two distinct objects occur together in exactly lambda blocks. Another way of defining a BIBD is in terms of its incidence matrix, which is a v by b binary matrix with exactly r ones per row, k ones per column, and with a scalar product of lambda between any pair of distinct rows. A BIBD is therefore specified by its parameters (v,b,r,k,lambda). An example of a solution for (7,7,3,3,1) is:

0 1 1 0 0 1 0
1 0 1 0 1 0 0
0 0 1 1 0 0 1
1 1 0 0 0 0 1
0 0 0 0 1 1 1
1 0 0 1 0 1 0
0 1 0 1 1 0 0

Interest : This problem and its modelisation are simple but the resolution is very complex and contains a lot of symmetries.

Sources :

Model :
The matrix is a list of v objects which are itself a list of b blocks. Each element of the matrix have the value 0 if the object no belongs to the block and 1 otherwise.
Source code :
The code is in GNU-Prolog.
Main predicat : bibd/5 (for instance bibd(Solution,V,B,R,K,Lambda), with V,B,R,K,Lambda instancied, Solution is the solution as lists of lists of 0 and 1 like above).
Help predicat : findInstance/1 helps to find some instance of bibd problem which has solution. Indeed some necessary conditions are known :
r.v=b.k
lambda.(v-1)=r.(k-1)
b>=v
Two models are implemented. The first one with scalar product constraints which generate a lot of new variables and auxiliar constraints (for the product scalar [X1,X2...].[Y1,Y2..]#=Lambda, the algoritm generates intermediate constraints X1.Y1#=Z1, X2.Y2#=Z2, ..., PS#=Z1+Z2 ...). The second uses the global constraint fd_cardinality/2. For switch from to other it just necessary to comment an appropriate line (see code).
Codeine trace :