ILP图循环检测
ILP graph cycle detection
我完全被这个（整数）线性规划公式任务困住了：
输入：包含环的有向边加权图。
目标：找到一组边，它们的权重总和最小，这样如果从图中删除这些边，图就会变成非循环的。
编辑： 对于任何感兴趣的人，我发现（在我朋友的帮助下），您可以使用拓扑排序来解决这个问题。您只需要为每条边引入一个约束，这样：
topologicalOrder[ edge.parent ] << topologicalOrder[ edge.child ] + ( M * edgeInactive[edge])
其中 topologicalOrder[node] 是节点拓扑位置的整数数组，edgeInactive 是布尔数组，表示边在结果（非循环）图中是否处于活动状态。
M 是用于在 edgeActive[edge] == true.
时“关闭”约束的 Big M 方法
然后你只需要最小化非活动边缘的权重总和。
旧（较慢）解决方案：
我的想法是创建节点的拓扑排序（对于非循环图，在拓扑排序时，所有边将按从左到右的方向排列），但是当我得到带循环的图时，我将寻找总和的拓扑排序从右到左的边数最少。
这种方法可行，但速度很慢...
（我正在尝试用 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 难问题：minimum feedback arc set. At least this answer 表明了这一点。
您可能会使用此关键字找到更多资源。
我记得当我在 Kemeny–Young method
上做一些 ILP 工作时，我读过关于 以上 问题的 ILP 公式
在 Google 上快速查找它，学者将我们带到：
Ali, Alnur, and Marina Meilă. "Experiments with Kemeny ranking: What works when?." Mathematical Social Sciences 64.1 (2012): 28-40.
其中说：
"The above ILP formulation has been given before [10, 28]. This formulation can also be interpreted as solving the minimum weighted feedback arc
set problem from computer science [10, 19]"
我猜你可能会从这篇论文开始 (Link to pdf as referenced by Google Scholar)
我发现（在我朋友的帮助下），你可以使用拓扑排序来解决这个问题。您只需要为每条边引入一个约束，这样：
topologicalOrder[ edge.parent ] << topologicalOrder[ edge.child ] + ( M * edgeInactive[edge])
其中 topologicalOrder[node] 是节点拓扑位置的整数数组，edgeInactive 是布尔数组，表示边在结果（非循环）图中是否处于活动状态。
M 是用于在 edgeActive[edge] == true.
时“关闭”约束的 Big M 方法
然后你只需要最小化非活动边缘的权重总和。
我完全被这个（整数）线性规划公式任务困住了：
输入：包含环的有向边加权图。
目标：找到一组边，它们的权重总和最小，这样如果从图中删除这些边，图就会变成非循环的。
编辑： 对于任何感兴趣的人，我发现（在我朋友的帮助下），您可以使用拓扑排序来解决这个问题。您只需要为每条边引入一个约束，这样：
topologicalOrder[ edge.parent ] << topologicalOrder[ edge.child ] + ( M * edgeInactive[edge])
其中 topologicalOrder[node] 是节点拓扑位置的整数数组，edgeInactive 是布尔数组，表示边在结果（非循环）图中是否处于活动状态。
M 是用于在 edgeActive[edge] == true.
时“关闭”约束的 Big M 方法
然后你只需要最小化非活动边缘的权重总和。
旧（较慢）解决方案：
我的想法是创建节点的拓扑排序（对于非循环图，在拓扑排序时，所有边将按从左到右的方向排列），但是当我得到带循环的图时，我将寻找总和的拓扑排序从右到左的边数最少。
这种方法可行，但速度很慢...
（我正在尝试用 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 难问题：minimum feedback arc set. At least this answer 表明了这一点。
您可能会使用此关键字找到更多资源。
我记得当我在 Kemeny–Young method
上做一些 ILP 工作时，我读过关于 以上 问题的 ILP 公式在 Google 上快速查找它，学者将我们带到：
Ali, Alnur, and Marina Meilă. "Experiments with Kemeny ranking: What works when?." Mathematical Social Sciences 64.1 (2012): 28-40.
其中说：
"The above ILP formulation has been given before [10, 28]. This formulation can also be interpreted as solving the minimum weighted feedback arc set problem from computer science [10, 19]"
我猜你可能会从这篇论文开始 (Link to pdf as referenced by Google Scholar)
我发现（在我朋友的帮助下），你可以使用拓扑排序来解决这个问题。您只需要为每条边引入一个约束，这样：
topologicalOrder[ edge.parent ] << topologicalOrder[ edge.child ] + ( M * edgeInactive[edge])
其中 topologicalOrder[node] 是节点拓扑位置的整数数组，edgeInactive 是布尔数组，表示边在结果（非循环）图中是否处于活动状态。
M 是用于在 edgeActive[edge] == true.
时“关闭”约束的 Big M 方法
然后你只需要最小化非活动边缘的权重总和。