Solutions and metaheuritics for 2-designs

1 BIBD: Formulation

A BIBD can be specified with five parameters ⟨v,b,r,k,λ⟩. Using this notation, a ⟨v,b,r,k,λ⟩-BIBD problem consists of dividing a set of v objects into b subsets of k < v objects each, such that each object belongs to r different subsets and any pair of objects appear together in exactly λ < b subsets. A standard way of representing the solution to such a problem –termed here as the primal (or binary) model (B)– is in terms of its incidence matrix M ≡{m_ij}_v×b, which is a v × b binary matrix where m_ij ∈{0,1} is equal to 1 if the ith object is contained in the jth block, and 0 otherwise; thus, it is easy to see that each row corresponds to an object and each column to a block, and that a matrix representing a feasible solution has exactly r ones per row, k ones per column, and the scalar product of any pair of different rows is λ.

Then the problem of finding a BIBD solution can be formulated as follows:

(1)

where

The dual formulation of the BIBD problem corresponds to a relaxed CSP problem defining an objective function that accounts for the number and degree of violations of constraints defined only on two parameters k and λ. Basically the solution (or candidate) to the BIBD is now defined by a dual incidence matrix M^d ≡{m_ij^d}_v×r, which is a v × r integer matrix where m_ij^d ∈ ℕ_b⁺ contains a value from the range [1,b] that identifies a block containing the object i. Note that there are r columns (i.e., j ∈ [1,r]), so that each object i is contained exactly in r blocks (in the case that one considers to impose an all-different constraint in the list of values of each row in the incidence matrix).

(5)

such that

(6)

where

In Eq. (7) and Eq. (8) we employ the Iverson brackets [] (i.e., [P]=1 if P is true, and 0 otherwise).

In this work we have addressed 86 instances commonly attacked by different techniques shown in the literature [1, 2], (see the Table 1). For more details check [3].

2 BIBD: Solution

2.1 For Basic and integrative approaches