Symmetry in integer programming.

This thesis focuses on solving integer programs whose feasible regions are highly symmetric. Symmetry has long been considered a curse in integer programming, and auxiliary (often extended) formulations are sought to reduce the amount of symmetry in an integer linear programming (ILP) formulation. The approach taken in this work is different in that it seeks to exploit the symmetry, not avoid it by reformulation. A standard method for solving integer programs is branch-and-bound . In branch-and-bound, the set of feasible solutions is partitioned, forming more easily-solved subproblems. The presence of symmetry means that many of these subproblems are equivalent in a sense we describe later. Only one member of each collection of equivalent subproblems needs to be solved. Failure to recognize that many subproblems are equivalent results in a waste of computational effort that can render an instance unsolvable by branch-and-bound. In an effort to reduce the deleterious effects of symmetry, we first introduce orbital branching, a branching method effective for binary integer programs exhibiting symmetry. This method is based on computing sets of variables that may be equivalent with respect to the symmetry in the subproblems created by branching (including symmetry that is introduced by such branching). These sets of equivalent variables, called orbits , are used to create a valid partitioning of the feasible region that significantly reduces the effects of symmetry. We also show how to use the symmetry present in the problem to fix variables throughout the branch-andbound tree. Orbital branching is an effective symmetry-breaking algorithm that can be easily incorporated into standard integer programming software. Orbital branching considers the effects of symmetry during the branching process. Fixing one variable through branching can often lead to the fixing of other variables as a result of symmetry. The additional variables that can be fixed by symmetry can have a significant effect on the LP relaxation solution and should be taken into account in the branching process. Through an empirical study on a test suite of symmetric integer programs, we investigate the question as to the most effective orbit on which to base the branching decision. The resulting method was shown to be quite competitive with a similar one known as isomorphism pruning and significantly better than a state-of-the-art commercial solver on symmetric integer programs. Another important contribution of this work is that it offers a way to identify and exploit the symmetry that arises in the problem as a result of branching decisions. Orbital branching does not, by itself, fully exploit the symmetry present in the problem. Specifically, some redundant subproblems may still be explored. Orbital branching can be a very effective method for finding an optimal solution. However, because there is no guarantee that all solutions found will be non-isomorphic, it is not recommended as a method of generating all non-isomorphic solution. Determining if the set of solutions contains only non-isomorphic solutions requires a comparison of each pair of solutions generated. The time needed to perform these tests could outweigh most of the benefits of using orbital branching. The second major contribution of this work is the development of a modification to isomorphism pruning, the current state-of-the-art symmetry-breaking technique for ILP. Isomorphism pruning provides a way to prune nodes and set variables in a way that guarantees that no two of the subproblems are symmetric. However, the current implementation of isomorphism pruning in ILP requires a very rigid branching...