Refine
Year of publication
- 2013 (2)
Document Type
- In Proceedings (1)
- ZIB-Report (1)
Language
- English (2)
Is part of the Bibliography
- no (2)
Keywords
- facet classification (1)
- polyhedral structure (1)
- symmetry (1)
Institute
The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled a tour
is evaluated by taking also preferences into account which
address the sequence in which the targets are visited. The
problem thus is a combination of two well-known combinato-
rial optimization problems: the traveling salesman and the
linear ordering problem. In this paper we present several
possible IP-Models for this problem and compared them to
their usability for branch-and-cut approaches.
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.