**Outils pour l'Analyse Dynamique et la mise au Point de**

**Programmes avec Contraintes**

## Classical examples

## 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 :**
*First model :*

bibd(R,3,6,4,2,2)(119k): all solutions, small instance.

bibd(R,4,6,3,2,1)(1.1M): all solutions, high instance.

*Second model :*

bibd(R,3,6,4,2,2)(132k): all solutions, small instance.

bibd(R,4,6,3,2,1)(1.3M): all solutions, high instance.