خصوصیات جنبه های چند ضلعی زنجیره ای محدود شده توسط برنامه های پویا

In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)(s,t)-chains using at most kk arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore–Bellman–Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result in characterizations of all facet defining 0/±10/±1-inequalities for the hop constrained chain polytope and all facet defining 0/10/1-inequalities for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper by Dahl and Gouveia in 2004.