This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).
The goal of this proposal is to develop a means for using integer programming efficiently to search for combinatorial objects. Integer programming is one of the most powerful techniques developed by the computer science and operations research communities for computationally solving combinatorial optimization problems. However, solving integer programs using linear programming relaxations does not perform well when searching for a combinatorial object with a specified isomorph-invariant property. Every isomorphic copy of the desired object also has the specified property, and, counter-intuitively, the presence of many objects with the desired property significantly slows the standard solving techniques of branch-and-bound and cutting planes. Additionally, the integrality condition often means the rational relaxation is not a good approximation to the integer program. The proposed work focuses on two new methods to address the difficulties caused by symmetry and divisibility conditions: rejecting isomorphic nodes from the branch-and-bound search tree through the use of symmetry-breaking orbital cuts, and using modular relaxations where the linear constraints are considered modulo a prime.
Combinatorial objects such as graphs, codes, and designs are important mathematical structures that appear in many disciplines, including computer science, operations research, and information technology. The proposed work includes searching for combinatorial objects using the powerful and well-known computational technique of integer programming. The PI proposes new methods for increasing the effectiveness of integer programming when used for combinatorial search. The resulting framework and computer code are intended to be used as a general tool for exploration and experimentation of a wide range of combinatorial objects.
