Exploiting Orbits in Symmetric ILP.pdf.pdf' (223.77 kB)
Download file

Exploiting Orbits in Symmetric ILP

Download (223.77 kB)
journal contribution
posted 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.




Usage metrics