0

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

问题是当节点数量很高时（例如：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.

在运行算法之前，如何预测给定节点数量的特定成本值是否太高？这将允许我适当地选择比例因子，以防止运行时失败。

4

1 回答 1

0

CostValue定义为typedef int64 CostValue
src：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

于 2018-06-13T11:11:47.593 回答