Branch-and-cut for symmetrical ILPs and combinatorial designs

摘要: Many combinatorial problems can be formulated as a 0-1 integer linear program (0-1 ILP), which consists of an objective function subject to constraints over variables. A method called branch-and-cut has been successfully used attack ILPs, but ILPs are still difficult solve in practice. The we investigate demonstrate large numbers equivalent (isomorphic) solutions. We only interested generating one solution from each equivalence class. To accomplish this, study and extend by Margot [22] that avoids considering unnecessary partial solutions isomorph-free search tree. implement library, design involving t-designs, packings, coverings intersecting set systems. experimentally analyze the strengths limitations our algorithms determine when it is efficient use branch-and-cut. Our framework generates new results reproduces, competitive time, existing ones.