标签: linear-programming

有一个大小为N x M的网格.一些细胞是由'0'表示的岛,而其他细胞是水.每个水电池上都有一个数字,表示在该电池上制造的电桥的成本.您必须找到所有岛屿可以连接的最低成本.如果单元共享边或顶点,则单元连接到另一个单元.

可以用什么算法来解决这个问题？
编辑:如果N,M的值非常小,可以用作蛮力方法,比如说NxM <= 100？

示例:在给定图像中,绿色单元格表示岛屿,蓝色单元格表示水,浅蓝色单元格表示应在其上制作桥梁的单元格.因此,对于下面的图像,答案将是17.

最初我想到将所有岛屿标记为节点并用最短的桥连接每对岛屿.然后问题可以减少到最小生成树,但在这种方法中我错过了边缘重叠的情况.例如,在下图中,任意两个岛之间的最短距离为7(标记为黄色),因此通过使用最小生成树,答案为14,但答案应为11(以浅蓝色标记).

是否有适用于Python的混合整数线性规划(MILP)求解器？

GLPK python可以解决MILP问题吗？我读到它可以解决混合整数问题.
我对线性编程问题很新.所以我很困惑,如果混合整数规划与混合整数线性规划(MILP)不同,则无法区分.

我正在使用CPLEX来解决巨大的优化模型(超过100k变量)现在我想看看我是否能找到一个开源替代品,我解决了混合整数问题(MILP)和CPLEX工作得很好但是如果我们这样做很贵想要扩展所以我真的需要找到一个替代方案或开始编写我们自己的ad-hoc优化库(这将是痛苦的)

任何建议/见解将不胜感激

我需要制作线性编程模型.以下是我正在使用的不等式(例如):

6x + 4y <= 24
x + 2y <= 6
-x + y <= 1
y <= 2

我需要找到由这些不等式描述的区域,并在图形中对其进行着色,以及跟踪该区域的边界线的顶点,并以不同的颜色绘制边界线.请参阅下图,了解我正在寻找的内容.

.

我正在使用Python 3.2,numpy和matplotlib.在Python中是否有更好的线性编程模块？

我正在尝试建立一个线性程序,其中目标函数max为决策变量中的各个系数增加额外的权重.

考虑到这一点,是有办法使用的方式min或max运营商内部线性规划的目标函数？

例:

Minimize
    (c1 * x1) + (c2 * x2) + (c3 * x3) + (c4 * max(c1*x1, c2*x2, c3*x3)) 
subject to
    #some arbitrary integer constraints:
    x1 >= ...
    x1 + 2*x2 <= ... 
    x3 >= ...
    x1 + x3 == ...

请注意,这(c4 * max(c1*x1, c2*x2, c3*x3))是我关注的"额外重量"一词.我们让c4表示"额外重量"系数.另外,还要注意x1,x2和x3是整数,在这个特殊的例子.

我认为上述内容可能超出了线性编程提供的范围.但是,也许有办法将其破解/重新格式化为有效的线性程序？

如果这个问题完全超出了线性规划的范围,也许有人可以推荐一种更适合这类问题的优化范例？(任何允许我避免手动枚举和检查所有可能的解决方案的东西都会有所帮助.)

这个问题出现在一个挑战中,但由于它现在已经关闭,因此可以询问它.

问题(不是这个问题本身,这只是背景信息)可以像这样直观地描述,借用他们自己的图像:

我选择以最佳方式解决它.这可能(对于决策变量)是NP完全问题(它肯定在NP中,它闻起来像一个精确的封面,虽然我还没有证明一般的确切覆盖问题可以减少到它),但是没关系,它只需要在实践中快速,不一定在最坏的情况下.在这个问题的上下文中,我对任何近似算法都不感兴趣,除非它们提供削减.

有一个明显的ILP模型:生成所有可能的正方形(如果它只覆盖存在的网格单元格,则x_i可以使用正方形),为每个正方形引入一个二进制变量,指示我们是否使用它,然后

minimize sum x_i

subject to:
1) x_i is an integer
2) 0 ? x_i ? 1
3) for every cell c
       (sum[j | c ? square_j] x_j) = 1

约束3表示每个细胞只被覆盖一次.约束1和2使x_i成为二进制.最小解决方案为原始问题提供了最佳解决方案.

这种线性松弛(即忽略约束1)是不太合适的,但它做了这样的事情(这是一个6x6网格,左上角缺失):

这里有13个方块被选为"一半"(给出一个6.5的目标值),大小(所以你可以更容易找到它们)

• 1x of 4x4
• 3x3中的3
• 6x2x2
• 1x1中的3个

此实例的最佳解决方案的目标值为8,例如:

线性放松是一半体面,但我并不完全满意.差距有时超过10%,有时会导致非常缓慢的整数阶段.

那是实际问题的来源,是否有额外的限制,我可以添加(懒惰)作为削减,以改善分数解决方案？

我已经尝试了问题的替代配方来寻找切割,例如,而不是选择正方形,如果我们选择"左上角"和"右下角",然后匹配形成非重叠方块覆盖所有细胞？然后在每个"反斜杠状对角线"上,必须有匹配数量的左上角和右下角.但这没有用,因为如果我们选择正方形,那么无论如何,这种情况总是正确的,也是在分数解决方案中.

我还尝试了一些关于重叠的推理,例如,如果两个正方形明显重叠,它们的总和不得大于1,并且可以通过添加完全包含在重叠区域中的所有正方形来改善.但是这种约束不如所有细胞只被覆盖一次的约束力强.

我已经尝试过关于总面积的推理(例如,总覆盖面积必须等于单元格的数量),但是已经通过约束来保证,每个单元必须覆盖一次,并根据总面积来说明只允许更多的自由.

我也尝试用方形数字(每个方格的面积,正好,正方形)和方形数字的差异做一些事情,但这并没有以任何有用的方式结束.

我是整数线性编程的新手.我计划使用整数线性编程求解器来解决我的组合优化问题.我更熟悉IDE上的C++ /面向对象编程.现在我使用NetBeans和Cygwin一起编写我的应用程序.

我可以问一下,对我来说是否有一个简单易用的ILP求解器？或者这取决于我想解决的问题？我正在尝试做一些资源映射优化.如果需要任何进一步的信息,请告诉我.

非常感谢,Cassie.

我想建立一个大的线性编程模型来解决一个有趣的问题.我最熟悉Java.有哪些工具/库？

快速搜索"python线性编程"会产生大量的点击(例如这一点).通过它们,我看到了相当多的关于过时的依赖关系,糟糕的文档等的抱怨.

任何人都可以为python推荐一个没有头痛的(例如快速,文档齐全,易于安装,干净的API)线性编程库吗？

我正在开发一种应用程序,可以最佳地为医院的护士分配班次.我认为这是一个带离散变量的线性规划问题,因此可能是NP难的:

• 对于每一天,每位护士(约15-20岁)都会被分配轮班
• 有少量(约6个)不同的班次
• 有相当多的约束和优化标准,无论是关于一天,还是关于一个emplyoee,例如:
  • 每天必须为每个轮班分配最少数量的人员
  • 有些班次重叠,所以如果有人做中间班,可以让一个人在早班换一个人
  • 有些人更喜欢提前班次,有些人更喜欢延迟班次,但需要最少的换班才能获得更高的轮班工资.
  • 不允许一个人一天工作到第二天工作到第二天早班(由于最短的休息时间规定)
  • 满足指定的工作周长度(不同的人不同)
  • ...

因此,基本上存在大量(约20*30 = 600)变量,每个变量可以采用少量离散值.

目前,我的计划是使用修改后的Min-conflicts算法

• 从随机分配开始
• 每个人和每一天都有健身功能
• 选择具有最差健身值的人或日
• 随机选择该日/人的任务之一并将其设置为导致最佳适合度值的值
• 重复直到达到最大迭代次数或者找不到所选日期/人的改进

有更好的想法吗？我有点担心它会陷入局部最佳状态.我应该使用某种形式的模拟退火吗？或者不仅考虑一次改变一个变量,而且特别考虑两个人之间的转换(当前手动算法中的主要部分)？我想避免将算法定制到当前约束,因为那些可能会改变.

编辑:没有必要找到严格的最佳解决方案; 名单目前是手工完成的,我很确定结果在大多数时候都是非常不理想的 - 不应该难以击败.短期调整和手动覆盖也一定是必要的,但我不认为这是一个问题; 将过去和手动分配标记为"已修复"实际上应该通过减少解决方案空间来简化任务.