HUHFA: A Framework for Facet Classification
Please always quote using this URN: urn:nbn:de:0297-zib-42230
- Usually complete linear descriptions of polytopes consist of an enormous number of facet-defining inequalities already for very small problem sizes. In this paper, we describe a method for dividing the inequalities into equivalence classes without resorting to a normal form. Within each class, facets are related by certain symmetries and it is sufficient to list one representative of each class to give a complete picture of the structural properties of a polytope. We propose an algorithm for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem.
Download full text files
Additional Services
| Author: | Olga Heismann, Achim Hildenbrandt, Francesco Silvestri, Gerhard Reinelt, Ralf BorndörferORCiD |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | facet classification; polyhedral structure; symmetry |
| MSC-Classification: | 52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B15 Symmetry properties of polytopes |
| 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68-04 Explicit machine computation and programs (not the theory of computation or programming) | |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
| Date of first Publication: | 2013/08/30 |
| Series (Serial Number): | ZIB-Report (13-45) |
| ISSN: | 1438-0064 |
