A polyhedral algorithm for packings and designs (Q4938787)

A \(t\)-\((v,k,\lambda)\) packing design (constant weight error-correcting code) is a collection of \(k\)-element sets (called blocks) out of a \(v\)-set such that each \(t\)-subset of the \(v\)-set is contained in at most \(\lambda\) blocks. The packing number, \(D_{\lambda}(v,k,t)\), is the maximum number of blocks in a packing design. A design is simple if it contains no repeated blocks. The author presents a polyhedral algorithm for finding packing numbers. Only simple packing designs are considered. Since \(t\)-designs are packings attaining the first Johnson bound (also called the Schönheim bound), the algorithm can also be used to search for these. When \(\lambda = 1\), the problem of finding a packing number is an instance of the problem of finding the size of a maximum clique (or a maximum independent set) in a graph. When \(\lambda > 1\), we get an instance of a more general problem. These observations are used in the branch-and-cut algorithm presented. The algorithm is sped up by fixing blocks and using partial isomorph rejection. No comparison against other approaches is carried out, but many tables of computational results are presented which will be useful in future comparisons. All test results are for \(\lambda = 1\); it is not clear how well the algorithm performs when \(\lambda > 1\). For the entire collection see [Zbl 0918.00032].