Exploiting Orbits in Symmetric ILP
journal contributionposted on 01.07.1979, 00:00 authored by Francois MargotFrancois Margot
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.