我完全被这个(整数(线性规划公式化任务卡住了：
输入：包含循环的有向边加权图
目标：找到一组边，这些边的权重之和最小，这样，如果从图中删除这些边，图就会变成非循环的。
编辑：对于任何感兴趣的人，我发现(在朋友的帮助下(，你可以使用拓扑排序来解决这个问题。您只需要为每条边引入一个约束，这样：topologicalOrder[ edge.parent ] << topologicalOrder[ edge.child ] + ( M * edgeInactive[edge])
其中topologicalOrder[node]是节点拓扑位置的整数数组，edgeInactive是布尔数组，表示边在生成的(非循环(图中是否活动。CCD_ 4是大M方法；关闭"；当CCD_ 5
然后只需要最小化非活动边的权重总和。
OLD(较慢(解决方案：
我的想法是创建节点的拓扑排序(对于非循环图，当拓扑排序时，所有边都将从左到右定向(，但当我得到具有循环的图时，我将寻找这样的拓扑排序，即从右到左定向的边之和最小。
这种方法有效，但速度非常慢。。。
(我正试图用Gurobi来解决这个问题，但我认为这几乎是一个一般的线性规划公式化问题。(我的代码：
# 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)
如果有任何帮助，我们将不胜感激
这看起来像是一个(一般(NP难题：最小反馈弧集。至少这个答案表明了这一点。
您可能会找到更多使用此关键字的资源。
我记得当我在Kemeny–Young方法上做一些ILP工作时，我读到了关于上述问题的ILP公式
在Google Scholar上快速查找它将我们带到：
Ali、Alnur和Marina Meilă"Kemeny排名实验：什么时候有效"数学社会科学64.1(2012(：28-40。
它说：
"上述ILP配方已在[10，28]之前给出。这个公式也可以解释为求解最小加权反馈弧集合问题来自计算机科学[10，19]"；
我想你可以从这篇论文开始(链接到谷歌学者引用的pdf(
我发现(在朋友的帮助下(，可以使用拓扑排序来解决这个问题。您只需要为每条边引入一个约束，这样：topologicalOrder[ edge.parent ] << topologicalOrder[ edge.child ] + ( M * edgeInactive[edge])
其中topologicalOrder[node]是节点拓扑位置的整数数组，edgeInactive是布尔数组，表示边在生成的(非循环(图中是否活动。CCD_ 9是大M方法；关闭"；当CCD_ 10
然后只需要最小化非活动边的权重总和。