Refine
Year of publication
Document Type
- Article (7)
- In Proceedings (3)
- ZIB-Report (3)
Language
- English (13) (remove)
Is part of the Bibliography
- no (13)
Keywords
- VLSI-Design (1)
- computational complexity (1)
- facet classification (1)
- polyhedral structure (1)
- quadratic 0/1 optimization (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.