Exploiting orbits in symmetric Integer Linear Program

This paper describes components of a branch-and-cut algorithm for solving integer linear programs having a large symmetry group. It describes an isomorphism pruning algorithm and variable setting procedures using orbits of the symmetry group. Pruning and orbit computations are performed by backtracking procedures using a Schreier–Sims table for representing the symmetry group. Applications to hard set covering problems, generation of covering designs and error correcting codes are given.