Symmetry Detection in Integer Linear Programs

Symmetry has long been recognized as a major obstacle in integer programming. Unless properly recognized and exploited, the branch-and-bound tree generated when solving highly symmetric integer programs (IPs) can contain many identical subproblems, resulting in a waste of computational effort. Effective methods have been developed to exploit known symmetry. This thesis focuses on improving methods that compute the symmetry group of an IP. In the literature, computing the symmetry group of an IP is performed by generating a graph with a similar structure as the IP, and then computing the automorphism group of the graph. Unfortunately, these graphs may be much larger than the IP problem, resulting in a possible waste of computational resources. The approach of this thesis is to detect the group of an edge-colored graph generated by the IP. This avoids the need for additional nodes to track coefficients, reducing the search space. Actually finding the group will be done by adapting and expanding a symmetry detection algorithm to work with these edge-colored graphs.