Groupe d’études et de recherche en analyse des décisions

Orbitwise polyhedral representation conversion

David Bremner


Converting between the inequality and finite-generator representations of a convex polyhedron is both a fundamental problem in algorithmic geometry and a useful subroutine in various optimization techniques. Unfortunately many problems of interest remain out of reach for current conversion methods. In certain applications the output is both large and symmetric. This has motivated study of the problem of orbitwise representation conversion: instead of producing all of the output, one looks for at least one element in each orbit (under some natural symmetry group).

I will start by surveying existing methods for orbitwise enumeration. These can be broadly classified into methods based on recursive problem decomposition, and those that "symmetrize" standard methods based on pivoting and incremental construction.

One common theme in efficient implementations of existing methods is the use of invariants to avoid expensive isomorphism tests. Another approach to avoiding isometry tests, and also permitting a more straightforward use of perturbation, is to construct a linear approximation of a fundamental domain for the given symmetry group. I'll finish the talk by describing ongoing work using this fundamental domain approach in incremental and pivoting based algorithms.

Ce séminaire est organisé conjointement avec la section Montréal de la SCRO et financièrement appuyé par le programme de conférenciers itinérants de la SCRO.