Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming

Please always quote using this URN: urn:nbn:de:0297-zib-14914
  • In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k 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 into characterizations of all facet defining {0,+1,-1}-inequalities for the hop constrained chain polytope and all facet defining {0,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 of Dahl and Gouveia in 2004.

Download full text files

Export metadata

Author:Martin Grötschel, Rüdiger Stephan
Document Type:ZIB-Report
Tag:chains; dynamic programming; facets; hop constraints
CCS-Classification:G. Mathematics of Computing
Date of first Publication:2012/03/26
Series (Serial Number):ZIB-Report (11-54)
Licence (German):License LogoCreative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.