问题标签 [linear-programming]

问题

我正在研究 SAT 优化问题的一个特殊子集。对于那些不熟悉 SAT 和相关主题的人，这里是相关的 Wikipedia 文章。

没有非，它是合取范式。这很容易解决。但是，我试图最小化真实分配的数量，以使整个陈述成为真实。我找不到解决这个问题的方法。

可能的解决方案

我想出了以下方法来解决它：

1. 转换为有向图并搜索最小生成树，仅跨越顶点的子集。有 Edmond 的算法，但它给出了完整图的 MST，而不是顶点的子集。
   • 也许有一个版本的 Edmond 算法可以解决顶点子集的问题？
   • 也许有一种方法可以从可以用其他算法解决的原始问题构建图形？
2. 使用 SAT 求解器、LIP 求解器或穷举搜索。我对这些解决方案不感兴趣，因为我正试图将这个问题用作讲座材料。

问题

你有什么想法/意见吗？你能想出其他可行的方法吗？

我刚刚学习了求解线性程序的单纯形法，我试图理解它的对偶问题代表什么。

我了解解决双重问题的机制——我不需要帮助。我无法得到（即使在Wikipedia上阅读过它）是dual 中y变量的实际含义。

我想举一个例子，连同原始问题中的可变含义，以及我从对偶中得出的结论，并会请任何足够友善的人解释对偶中的含义：

原始：

在原始问题中，x1和x2是要生产的产品A和B的数量。3和5分别是它们的单位售价。产品在 3 台机器上生产，M1-M3。要生产第一个产品，需要在M1上工作1 小时，在M3上工作 3 小时。要制作第二个， M2和M3都需要两个小时的工作。机器M1、M2、M3最多可工作4、12和18小时，分别。最后，我不能生产负数量的任何产品。

现在，我设置了对偶问题：

现在，我想我唯一能弄清楚的是，这些限制意味着：-在M1上工作一个小时，在M3上工作3 小时，我应该得到至少 3 个货币单位的报酬-在M2和 2上工作两个小时在M3上几个小时，我应该得到至少 5 个货币单位的报酬

但是，我无法理解y1和y2变量的含义。当我最终进行最小化时，z中的结果在primal 中是相同的（尽管 primal 在增加结果的下限，而对偶正在减少上限），但是对偶问题的目标函数包括什么的？

我正在尝试实现一个具有键值结构对的系统。它们需要以某种线性方式保存（也就是说，它们可以被索引），一旦给定一个位置就不能移动，所以插入只能追加（实际上不能有太多的排序。）举个例子，这就是我的想法：

我已经设计了这样的系统，以便在搜索一个键时，它的索引可以被缓存，然后以恒定的时间访问。现在，由于我无法预测数据的顺序或数量，而且我无法对其进行排序，因此我需要关于算法或数据结构的想法，这些想法会比线性搜索更好，但仍然保持约束我'我喜欢。

有人有什么想法吗？我怀疑我能否加快速度，但每一点都会有所帮助，因为这将是我系统的核心。提前致谢！

==编辑==

使用两个独立结构（如哈希表和动态数组）的想法实际上是我的第一个意图。不幸的是，这对我不起作用，因为我无法分离键和值。键将用于错误和消息，因此即使缓存了索引，仍需要访问原始键。基本上它们必须只是一个数组结构，例如：

我在 Linux 下使用 GLPK 来解决一些线性规划问题。在我的限制之一中，我有：

哪里binary_val是定义为“二进制”的变量。

如果binary_val取值1，它的总和是2，还是二进制，它会返回0还是1？

我正在用 C++ 编写代码并调用 CPLEX 来解决它。它可以快速找到一个非常好的解决方案，但需要很长时间才能尝试改进它。所以我想将间隙设置为更大的值来终止代码，这就是我使用的：

但是编译器给了我一个错误，说EpGap是一个未声明的标识符。相对间隙的默认名称是什么？

我正在尝试解决matlab中的线性规划问题，输入是

因此，根据手册，这应该可以解决问题min f*x with the constraints C*x=b and 0<=x<=10。所以所有的条目都x应该是正数。但是，我得到的解决方案包含否定条目（请参阅示例以重现下面的问题）。我得到的标志是 1，根据文档，这意味着该方法已经收敛。

我究竟做错了什么？

这是输入

和

和

结果是

我正在运行线性模型来查看所涉及的独立因素的重要性。示例模型是：`

我查看摘要以检查每个因素的重要性：

现在，我想看看bgrp（1和2）和psex（1和2）这两个级别的解决方案。

如果您能帮我解决这个问题，我将不胜感激。

提前谢谢你，

巴兹

编辑：

我运行了您建议的第一个模型并得到以下结果：

从上面的系数表来看，bgrp1 和 bgrp2 似乎是有道理的：bgrp1 代表产仔数较大的母系，后代较轻，这导致后代的直肠温度较低（37.70 摄氏度）。另一方面，bgrp2 代表产仔数较小、后代较重的终端线，这导致直肠温度较高（37.98 摄氏度）。我只是想知道，是否可以对 psex1 和 psex2 执行相同的操作，但是系数表中显示的内容可能是由于您之前所说的。

编辑：嗨，马克，

我尝试了您建议的两个选项，我可以看到 bgrp1 和 psex1 具有相同的值：

谢谢！

二次编程库是否有任何 Haskell 绑定？

如果没有，假设我无法避免需要一个，我应该编写哪一个简化绑定？是否有一个合理规范的开源库？

我将制定一个我想用机器学习（在 R 或类似平台中）解决的简单问题：我的算法采用3 个参数（a、b、c），并返回[0,1] 范围内的分数s . 参数都是分类的：a 有 3 个选项，b 有 4 个，c 有 10 个。因此我的数据集有 3 * 4 * 10 = 120 个案例。高分是可取的（接近 1），低分不是（接近 0）。让我们将算法视为一个黑匣子，取 a,b,c 并返回 a s。

数据集如下所示：

如果我为每个参数绘制 s 的密度，我会得到非常广泛的分布，在某些情况下表现非常好 (s > .8 )，而在其他情况下表现不佳 (s < .2 )。

如果我查看 s 非常高的情况，我看不到任何清晰的模式。总体表现不佳的参数值与特定参数结合起来可以表现得非常好，反之亦然。

为了衡量特定值的执行情况（例如 a1），我计算了中位数：

例如，中位数（a1）=.5，中位数（b3）=.9，但是当我将它们组合时，我得到的结果 s(a_1,b_3)=.3 较低。另一方面，中位数(a2)=.3，中位数(b1)=.4，但 s(a2,b1)=.7。

鉴于没有总是表现良好的参数值，我想我应该寻找似乎一起表现良好的组合（2个参数），以统计学上显着的方式（即排除恰好具有非常高分数的异常值）。换句话说，我想获得一个策略来做出最佳参数选择，例如表现最好的组合是（a1，b3），（a2，b1）等。

现在，我想这是一个可以使用机器学习解决的优化问题。

在这种情况下，您会推荐哪些标准技术？

编辑：有人建议使用glpk的线性规划解决方案，但我不明白如何将线性规划应用于这个问题。

当我查看优化问题时，我看到了很多选项。一是线性规划。我从抽象的角度理解 LP 是如何工作的，但我发现很难看出一个特定的问题是否适合 LP。是否有任何启发式方法可以帮助指导这一决定？

例如，Is there a good way to do this type Mining 中描述的工作？我花了几周的时间才看到如何正确地构造问题。是否有可能“提前”知道问题可以由 LP 解决，而无需先看到“如何表达它”？

是否有我可以用来确定问题是否适合 LP 的清单？该主题是否有标准（可读）参考？