Title: Characterization of facets of the hop constrained chain polytope
using projection
Author: Rüdiger Stephan
Abstract:
We study polyhedra associated with hop constrained node-arc sequences,
that is, sequences that use at most $k$ arcs. The polyhedra are the
hop constrained path polytope, which is the convex hull of the
incidence vectors of directed $(s,t)$-paths using at most $k$ arcs,
and two of its relaxations: its dominant and the hop constrained chain
polytope, which has the same dominant as the hop constrained path
polytope.
Using DP-based extended formulations for the hop constrained chain
polytope and its dominant (precisely, one derived from the inherent
structure of the Moore-Bellman-Ford-algorithm), we determine some
useful necessary conditions for extreme rays of the projection cones
to correspond to facets.
Then, we use these informations to derive new facet defining
inequalities for the dominant by relaxing certain properties of
extreme rays corresponding to already known facet defining
inequalities (jump inequalities introduced by Dahl and Gouveia
(2004)). Since the projection cones for the hop constrained chain
polytope and the dominant are quite similar, we are also able to
transform these inequalities into facet defining inequalities for the
hop constrained chain polytope. Moreover, we give sufficient
conditions for the resulting inequalities to be facet defining for the
corresponding path polytope.