Experimental investigation of the polyhedral structure of balanced incomplete block designs

Abstract

We examine the polyhedral structure of Balanced Incomplete Block Designs (BIBDs) in an effort to improve runtimes for finding optimal solutions via constraint or integer program. For example, an optimal BIBD is one that minimizes the range of blocksums. This range, which we refer to as diffsum, has applications in drug trials and Redundant Arrays of Independent Disks (RAID). We present two models for imposing lexicographical order on the solutions to reduce the search space. The polytope we explore is the convex hull of all lexicographically-ordered BIBD solutions satisfying a given set of parameters, (v, b, r, k, λ), with solutions represented as a vector in Rkb. The dimension-reducing equations and the facets for some of the smaller polytopes were found by using the Double-Description Method on an algebraic program modelling these solutions. Because of the presence of the lexicographic ordering, none of these polytopes are full dimensional. After describing some of these smaller BIBD polytopes, we generalize some dimension-reducing equations, and evaluate the efficiency of these equations to optimization models. A third model is also presented that provides a complete, compact description of BIBDs