python - 与 Gurobi 一起解决奖品收集施泰纳树

Question

我是建模数学规划问题的新手。我正在尝试使用 Gurobi 求解器解决有关网络优化的练习。这就是练习所说的：

`附件中的图表graph10092015.gml包含一组电信公司可以与光纤网络连接的潜在机柜。每个机柜（节点）u 关联了一个利润，每个边 uv 关联了一个连接成本。

1. 设计一个使公司利润最大化的网络，因为链路安装的预算不能超过 4000 欧元。
2. 从之前的最优方案，评估将网络扩展到19号机柜的便利性，花费500欧元在机柜内安装无线路由器，免费连接4号机柜和14号机柜。`

我将问题表述为奖品收集施泰纳树：

问题的表述

你怎么看待这件事？为了解决这个问题，我应该使用切割平面方法并因此定义分离问题吗？

我想我知道如何为问题建模，但我仍然对这种类型的练习没有信心。

在此先感谢您的帮助。

Answer 1

我前段时间给出了这个问题的解决方案。我将此问题表述为 PCST。我添加了一个约束，该约束对设计网络的成本施加了上限（它模拟了要花费的预算）。

一旦我获得了第一点的解决方案。我引入了一个二进制变量 k，当为 1 时，可以抵消 4,14 机柜的成本，并在 19 处增加路由器安装成本。然后：

1- 我强制将 19 连接到点 1 处的树状结构。这等于：y[19] = 1

2- 如果橱柜 19 在树状结构中，那么即使是 4 和 14 也必须在其中。这等于：(2 * y[19]) <= y[4] + y[14]

3- 如果 19 在树状结构中，则引入路由器引起的成本变化。这等于：k[1] <= y[19]