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.