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?


asked 23 Oct '17, 12:15

OR-Mastery's gravatar image

accept rate: 0%

edited 23 Oct '17, 12:22

Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 23 Oct '17, 12:15

Seen: 290 times

Last updated: 23 Oct '17, 12:22

OR-Exchange! Your site for questions, answers, and announcements about operations research.