具有目标函数中的符号的最小成本最大流量

Question

我有一些Min-cost-max-flow问题，在约束条件下有简单的平衡方程，但在目标函数中有“坏”的符号，即，目标函数仅取决于沿边缘的流动的存在，而不是值。

我可以用U_i介绍bool变量U_i <= x_i约束U_i和重写目标函数，但它是混合整数编程模型。在我的实际数据中，变量的数量必须至少为10000，约束的行数也约为10000。

Q1：使用简单的分支和切割方法是否太慢？

Q2：保留模型线性度是否有任何技巧可以解决这个问题？ （我觉得答案不是）

问题3：那么，有没有有效的方法来解决这个问题？

Answer 1

1. 通常，二进制文件的约束看起来像 x(i) <= y(i)*capacity(i) 对于弧i，其中x(i)流动和y(i) ∈ {0,1}。这模仿了这个含义 y(i)=0 => x(i)=0
2. 即使在添加整数限制之后，也可以快速解决许多（但不是全部）具有网络结构的模型。你真的应该尝试一下（对于大多数关于性能的问题，这是最好的答案）。具有10k二进制变量的简单模型不会自动超出范围。使用一个好的MIP求解器。