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

Export metadata

  • Export Bibtex
Author:Olga Heismann, Achim Hildenbrandt, Francesco Silvestri, Gerhard Reinelt, Ralf Borndörfer
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)

$Rev: 13581 $