| DATE: | Thursday, March 27th |
| TIME: | 4:15 PM - 5:15 PM |
| PLACE: | McConnell 103 |
| TITLE: | Generating vertices and faces with symmetries |
| SPEAKER: | Antoine Deza, Tokyo Institute of Technology |
We study enumeration algorithms for polytopes that arise in combinatorial
optimization problems. Enumerating these polytopes is usually practically
intractable. But for specific problems, tailor-made algorithms, using the
polytopes' rich combinatorial features, can be very efficient. The main
engine of these combinatorial algorithms is the use of the large symmetry
group of combinatorial polytopes. We present an orbitwise vertex
enumeration algorithm to generate the 1 550 825 600 vertices of a highly
degenerate 28-dimensional polytope defined by its 224 facets. We describe
a promising heuristic that skips the highest degeneracies. A
generalization to an orbitwise face enumeration algorithm is presented.
Lastly, computational issues for the orbitwise vertex and face enumeration
algorithms are discussed.