Article ID: | iaor20032517 |
Country: | Germany |
Volume: | 94 |
Issue: | 1 |
Start Page Number: | 71 |
End Page Number: | 90 |
Publication Date: | Jan 2002 |
Journal: | Mathematical Programming |
Authors: | Margot F. |
Keywords: | sets |
The paper presents a branch-and-cut for solving (0, 1) integer linear programs having a large symmetry group. The group is used for pruning the enumeration tree and for generating cuts. The cuts are non-standard, cutting integer feasible solutions but leaving the optimal value of the problem unchanged. Pruning and cut generation are performed by backtracking procedures using a Schreier–Sims table for representing the group. Applications to hard set covering problems and to the generation of covering designs and error correcting codes are presented.