Possible cuts to remove cycles in a directed graph

 0 I'm working on a graph related problem. In my application, I'll firstly construct a directed graph by solving an optimization problem. Then, I detect if the directed graph contains any directed cycle via Johnson's algorithm. Finally, I want to remove directed cycles from the graph by imposing valid constraint and solve the problem again in an iterative fashion. Z_{jk} =1 if there is an arc from node j to node k, and 0, otherwise. My question is as follows: Given a directed graph which can contain directed cycles, what possible valid inequalities (i.e., constraints) we can impose to remove one or more directed cycles. There could be many possible inequalities. One example that came to my mind is as follows: First detect a directed cycle in a graph. Then construct a directed path from the cycle and impose this constraint: $$\sum_{(p,q)\in path} Z_{pq} \leq |path|−1$$ Any other suggestion? Thanks! asked 23 Oct '17, 12:15 OR-Mastery 11●2 accept rate: 0%
Be the first one to answer this question!
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: