Pruning by isomorphism in branch-and-cut

Pruning by isomorphism in branch-and-cut

0.00 Avg rating0 Votes
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:
Keywords: sets
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.