HUHFA: a framework for facet classification. 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.
Keywords for this software
References in zbMATH (referenced in 2 articles )
Showing results 1 to 2 of 2.
- Hildenbrandt, Achim: A branch-and-cut algorithm for the target visitation problem (2019)
- Lörwald, Stefan; Reinelt, Gerhard: PANDA: a software for polyhedral transformations (2015)