Symmetric Optimization

Meeting Time: Mar. 12, 2010, 10:30-11:10am, Avery 347

Abstract: Optimization problems are fundamental to mathematics and computer science. Symmetric optimization problems are interesting and difficult, appearing in several contexts such as the search for combinatorial objects. However, the standard techniques to solve optimization problems often fail in the presence of symmetry. This work examines symmetric optimization problems and applies new techniques to find solutions. These techniques include generalizing orbital branching, finding symmetric solutions using partial permutations, and designing cuts that break symmetry. Moreover, many existing heuristics will be integrated with symmetry-exploiting methods. The result will be a framework which finds solutions to symmetric optimization problems faster than the current state of the art and will be used to find or prove nonexistence of discrete objects whose existence is currently unknown.