68-04 Explicit machine computation and programs (not the theory of computation or programming)
Refine
Keywords
Institute
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.
An algorithm is described to decide if a given polynomial differential expression $\Delta$ of multivariate functions is exact, i.e. whether there exists a first integral $P$ such that $D_xP = \Delta$ for any one of a set of variables $x$ and to provide the integral $P$. A generalization is given to allow integration in the case that the exactness is prohibited by terms which contain only functions of not all the independent variables.