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
OR-Mastery |