On the Cycle Polytope of a Directed Graph and Its Relaxations

Egon Balas and Rüdiger Stephan ()
Additional contact information
Rüdiger Stephan: TU Berlin

A chapter in Operations Research Proceedings 2006, 2007, pp 203-208 from Springer

Abstract: Abstract This paper continues the investigation of the cycle polytope of a directed graph begun by Balas and Oosten [2]. Given a digraph G = (N,A) and the collection C of its simple directed cycles, the cycle polytope defined on G is P C ≔ conv {X C :C∈C}, where χ C is the incidence vector of C. According to the integer programming formulation given in [2], P C is the convex hull of points x∈ℝ satisfying (1) $$ x(\delta ^ + (i)) - x(\delta ^ - (i)) = 0{\text{ }}for{\text{ all }}i \in N $$ , (2) $$ x(\delta ^ + (i)) \leqslant 1{\text{ }}for{\text{ all }}i \in N $$ , (3) $$ \begin{array}{*{20}c} { - x(S,N\backslash S) + x(\delta ^ + (i)) + x(\delta ^ + (j)) \leqslant 1{\text{ }}for{\text{ all }}S \subseteq N,2 \leqslant |S| \leqslant n - 2,} \\ {i \in S,j \in N\backslash S} \\ \end{array} $$ , (4) $$ \sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = i + 1}^n {x_{\pi (i)\pi (j)} } \geqslant 1{\text{ for all permutations }}\pi {\text{ of }}N} $$ , (5) $$ x_{ij} \in \{ 0,1\} {\text{ }}for all (i,j) \in A $$

Keywords: Direct Graph; Linear Ordering; Valid Inequality; Linear Programming Relaxation; Incidence Vector (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-540-69995-8_34

Ordering information: This item can be ordered from
http://www.springer.com/9783540699958

DOI: 10.1007/978-3-540-69995-8_34

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().