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.
Author: | Martin Grötschel, Rüdiger Stephan |
---|---|
Document Type: | ZIB-Report |
Tag: | chains; dynamic programming; facets; hop constraints |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
CCS-Classification: | G. Mathematics of Computing |
Date of first Publication: | 2012/03/26 |
Series (Serial Number): | ZIB-Report (11-54) |
ISSN: | 1438-0064 |
Licence (German): | Creative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung |