HUHFA: A Framework For Facet Classification

The polyhedral approach to combinatorial optimization problems studies the structure of their associated polytopes. One way is to compute complete linear descriptions of small polytopes in order to generalize the equations and inequalities. "Small polytopes'' might actually not look so small at first sight: There is often a huge number of facet-defining inequalities already for very small problem sizes.

However, there are also often many symmetries implied by the combinatorial structure of the problem which can be used to classify the facets. These symmetries act on the feasible solutions and naturally form a group. In their representation as maps on the variable values they can be extended to symmetries acting on the polytope, and one can easily prove that they map vertices of the polytope to vertices of the polytope. We say that those facet-defining inequalities which are similar in the sense that they can be transformed onto each other by some symmetry belong to one class.

Understanding all the facet-defining inequalities of a combinatorial optimization problem polytope then reduces to understanding one facet from each class.

To do this classification, one applies the symmetries to the facet-defining inequalities and then checks whether any two facets can be transformed into each other and hence belong to the same class. Often, this check is not so easy as two linear expressions describing the same facet might differ by the sum of multiples of several equalities from the problem description.

The check can be accomplished by defining a so-called normal form for the representation of inequalities—inequalities which have the same normal form describe the same facet. To this end, problem-specific normal forms were developed for some extensively studied combinatorial optimization problems. In general, the representation of facet-defining inequalities in the orthogonal complement of the linear subspace spanned by the equations can be of course used as a normal form for the facets of a polytope. However, this needs techniques from linear algebra and can therefore raise numerical issues. Unfortunately, normal forms that can be described combinatorially are often not known. Hence, having a method that can be applied to every combinatorial optimization problem and relies solely on the combinatorial structure of the polytope is desirable.

HUHFA uses a novel technique for classifying facets without using normal forms. The main idea is to identify every facet defining inequality with the vertices of the polytope which satisfy it with equality. With this method, complete descriptions of polytopes computed by a software like PORTA (or a similar package) can be analyzed to divide the facets into equivalence classes according to groups generated by given symmetry mappings.

Download HUHFA source code and manual

More information on the theoretical background of how HUHFA works can be found in this paper.

HUHFA is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License Version 3 as published by the Free Software Foundation. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

For questions, bugs, remarks, etc. please contact Achim Hildenbrandt or Olga Heismann.