哪种算法可以为 1200 个站点找到最佳的两个网络连接选项？

Question

我是一名数据工程师，正在尝试解决一个有趣的分析问题。我已链接到一个包含示例数据的小型 Excel 工作簿。

问题陈述：

某公司在 1200 个地点设有分支机构。他们想要所有分支机构的网络连接。他们需要来自两个独立服务提供商的两种连接解决方案，以确保服务连续性。

有 20 多家服务提供商，每家提供多达 30 种连接产品。并非所有服务提供商都存在于所有位置，并且某些位置仅由供应商的部分产品覆盖。产品类型从最好到最差排名。

容量越大越好，但总体预算是一个制约因素。

为每个地点找到合适的供应商和产品是一个乏味的过程，尤其是在包含其他限制因素的情况下。

搜索表明 LTR 可能会使用 class 算法，但请指出任何更好的解决方案或方法。

Link to Workbook on Dropbox

谢谢，艾伦.

Answer 1

你的问题很小，只要代价函数不太复杂，你可以暴力破解。

您有 1200 个位置，每个位置有 20 个提供商，每个提供商有 30 个产品。您想从独立供应商那里为每个位置选择 2 个产品：(20*30 + 19*30) + 1200 = 140 万个解决方案进行分析。

你可以运行简单的回溯找到总成本最小的解，而且由于问题不是太大，应该只需要几秒运行。基本的伪代码可以是：

 bruteForce(partialAnswer, currentLocation, constraints, bestAnswer):
     for (each possible pairOfOfferings from different provicers at
               currentLocation):
         add pairOffering to partialAnswer
         if (pairOfOffering ok according to constraints):
             if (currentLocation is last location left):
                if (partialAnswer beats bestAnswer according to cost function):
                    update bestAnswer
             othwerwise:
                call bruteForce(
                         partialAnswer, nextLocation, constraints, bestAnswer)
         remove pairOffering from partialAnswer

P运行搜索 space 可以显着加快速度，但除非你有更多的位置，或者你真的需要亚秒级的响应时间，否则可能不会值得

Answer 2

这个问题似乎很适合整数规划。您可以向像 PuLP 这样的库描述变量、约束和 objective 函数，然后让库完成寻找最佳解决方案的肮脏工作。

Answer 3

这听起来 minimum-cost flow problem , for which the network simplex algorithm 在小范围内很难被击败。

MCFSimplex is probably the fastest open source network simplex implementation available, so that may be what you're looking for. And it has a Python wrapper。

哪种算法可以为 1200 个站点找到最佳的两个网络连接选项？

Which algorithm for finding best two options for network connectivity for 1200 sites?

algorithm

analytics