Exploiting symmetries in polyhedral computations

09/24/2013 - 12:15pm
09/24/2013 - 1:10pm
Achill Schuermann (University of Rostock)

Many important problems in mathematics and its applications are modeled using linear constraints, respectively polyhedra. Standard modeling often yields polyhedra having many symmetries. However, standard algorithms do not take advantage of them, and even worse, they often work particularly poorly on symmetric problems. In this talk we give an overview of ongoing work on new symmetry-exploiting techniques for three fundamental tasks in polyhedral computations: the representation conversion problem, integer linear programming, and lattice point counting. Initial proof-of-concept results show that affine symmetries can be exploited quite well in certain situations. In order to apply these new techniques on a broader scale new theoretical grounds have to be broken.

Mudd Science Library 126, Pomona College