ILP graph cycle detection

Question

I got totally stuck with this (integer) linear programming formulation task:
Input: directed edge-weighted graph which contains cycles.
Goal: find set of edges, with minimal sum of their weights, such that if these edges are removed from the graph, the graph becomes acyclic.

EDIT: for anyone interested,I found out (with a little help from my friends), that you can use topological ordering to solve this problem. You just need to introduce a constraint for each edge such that:
topologicalOrder[ edge.parent ] << topologicalOrder[ edge.child ] + ( M * edgeInactive[edge])
where topologicalOrder[node] is an integer array of topological positions of nodes and edgeInactive is array of bools denoting whether the edge is active in the resulting (acyclic) graph. M is the Big M method used for "turning off" the constraint when edgeActive[edge] == true.
Then you just need to minimize the sum of weights of inactive edges.

OLD (slower) solution:
My idea was to create a topological sorting of nodes (for an acyclic graph all edges would be oriented form left to right when topologically sorted), hovewer as I'm given graph with cycles I'll be looking for such topological ordering that the sum of edges directed from right to left is minimal.

This approach works but it's really slow...

(I'm trying to solve this problem with Gurobi but I think it's pretty much general Linear programming formulation problem.) My code:

# Variables
x = model.addVars(nodeCount, nodeCount, vtype=g.GRB.BINARY) # matrix of size nodeCount * nodeCount, where x[i,j] denotes if node i is topologically before node j

#Constraints
for e in edges:
    model.addConstr(x[e.child, e.parent] == 1 - x[e.parent, e.child])  # x[i,j] needs to be equal to negative value of x[j,i]

    for k in range(nodeCount):
        model.addConstr(  x[e.parent, e.child] + x[e.child, k] - x[e.parent, k] <= 1) # Without this constraint solver produced invalid ordering results so I came up with this equation. But I'm not sure if this is the best way to solve this issue..


# Objective
sumNegativeEdges = 0;
for e in edges:
    sumNegativeEdges+= (x[e.child, e.parent]) * e.weight; # Adding just weight of edges where child is topologically before the parent

model.setObjective(sumNegativeEdges, g.GRB.MINIMIZE) 

Would be grateful for any help...

Answer 1

I found out (with a little help from my friends), that you can use topological ordering to solve this problem. You just need to introduce a constraint for each edge such that:
topologicalOrder[ edge.parent ] << topologicalOrder[ edge.child ] + ( M * edgeInactive[edge])
where topologicalOrder[node] is an integer array of topological positions of nodes and edgeInactive is array of bools denoting whether the edge is active in the resulting (acyclic) graph. M is the Big M method used for "turning off" the constraint when edgeActive[edge] == true.
Then you just need to minimize the sum of weights of inactive edges.