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.