Tag: 线性规划

最好的开源混合整数优化求解器

我正在使用CPLEX来解决巨大的优化模型（超过10万个variables），现在我想看看是否可以find一个开源替代scheme，我解决混合整数问题（MILP）和CPLEX的工作很好，但是如果我们想要扩展，所以我真的需要find一个替代或开始写我们自己的特设优化库（这将是痛苦的） 任何build议/见解将不胜感激

连接所有岛屿的最低成本是多less？

有一个大小为N×M的网格。 一些细胞是由“0”表示的岛 ，其他是水 。 每个水细胞上都有一个数字，表示在该细胞上制造的桥梁的成本。 你必须find所有岛屿可以连接的最低成本。 如果单元格共享边或顶点，则该单元格将连接到另一个单元格。 什么algorithm可以用来解决这个问题？ 编辑：如果N，M的值非常小，比如说NxM <= 100，那么什么可以用作蛮力方法呢？ 例如 ：在给定的图像中，绿色的单元格表示岛屿，蓝色的单元格表示水，浅蓝色的单元格表示应在其上创build桥梁的单元格。 因此对于下面的图片，答案将是17 。 起初我想把所有的岛屿都标记为节点，并用最短的桥梁连接每一对岛屿。 然后问题可以减less到最小生成树，但在这种方法中，我错过了边缘重叠的情况。 例如 ，在下图中，任意两个岛之间的最短距离是7 （用黄色标记），所以使用最小生成树的答案是14 ，但答案应该是11 （用浅蓝色标记）。