On cardinality constrained cycle and path polytopes
Please always quote using this URN: urn:nbn:de:0297-zib-10093
- We consider polytopes associated with cardinality constrained path and cycle problems defined on a directed or undirected graph. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. Moreover, we give further facet defining inequalities, in particular those that are specific to odd/even paths and cycles.
Author: | Volker Kaibel, Rüdiger Stephan |
---|---|
Document Type: | ZIB-Report |
Tag: | cycles; facets; integer characterizations; path |
MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C38 Paths and cycles [See also 90B10] |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut | |
Date of first Publication: | 2007/10/02 |
Series (Serial Number): | ZIB-Report (07-25) |
ISSN: | 1438-0064 |
ZIB-Reportnumber: | 07-25 |
Published in: | Appeared in: On cardinality constrained cycle and path polytopes Math. Program. (Ser. A) 123 (2), 2010, 371-394 |