在 MinCostFlow 求解器中，如果最大成本幅度过高，我如何才能预先预测？

Question

我在程序中使用 Google OR-tools 库 (v6.4)（特别是库中的 MinCostFlow class）。根据我的要求，我的成本矩阵由浮点值组成。然而，由于此 class 的实例只能接受具有整数成本的弧，我将每个成本乘以 10 的幂的比例因子（10¹⁶，在时刻），然后将其作为弧的成本传递。

问题是当节点数量很多时（例如：10000 个源和 10000 个汇），我在运行时收到以下错误：

E0612 12:08:45.378520 231034880 min_cost_flow.cc:237] Maximum cost magnitude 9999999857054488 is too high for the number of nodes. Try changing the data.

在运行算法之前，如何根据节点数量预测特定成本值是否过高？这将允许我适当地 select 缩放因子，以防止在运行时失败。

Answer 1

CostValue 定义为 typedef int64 CostValue
来源：https://github.com/google/or-tools/blob/9487eb85f4620f93abfed64899371be88d65c6ec/ortools/graph/ebert_graph.h#L204

计算此检查的代码是：

CostValue max_cost_magnitude = 0;
// Traverse the initial arcs of the graph:
for (ArcIndex arc = 0; arc < graph_->num_arcs(); ++arc) {
  const CostValue cost_magnitude = MathUtil::Abs(scaled_arc_unit_cost_[arc]);
  max_cost_magnitude = std::max(max_cost_magnitude, cost_magnitude);
  ...
}
...
if (log(std::numeric_limits<CostValue>::max()) <
  log(max_cost_magnitude + 1) + log(graph_->num_nodes() + 1)) {
 LOG(FATAL)...;
}

来源：https://github.com/google/or-tools/blob/9487eb85f4620f93abfed64899371be88d65c6ec/ortools/graph/min_cost_flow.cc#L235

在 MinCostFlow 求解器中，如果最大成本幅度过高，我如何才能预先预测？

In the MinCostFlow solver, how can I predict beforehand if the maximum cost magnitude is too high?

or-tools