问题标签 [linear-programming]

在多年使用 Matlab 之后，我对 Python 还是很陌生。我正在尝试使用 Pulp 来建立一个整数线性程序。

给定一个数字数组：

我想最大化：

受约束

并且有边界（基于向量的边界）

然而，在纸浆中，我看不到如何正确地进行向量声明。我正在使用：

我只能输入个人界限（所以只有1个数字）。

对于约束，我真的必须每行都做这一行吗？看来我错过了什么。我会很感激一些帮助。该文档讨论了一个简短的示例。在我的例子中，变量的数量是几千个。

这个问题来自我在此处发布的一个相关问题。@mhum 建议我的问题属于覆盖问题域。我尝试将我的问题编码为最小集覆盖问题，目前我有一个这种形式的数据集：

目标是找到一个覆盖所有数字的好的集合覆盖，并试图最小化总成本。我的数据集很大，至少有 30000 个集合（大小从 5-40 个元素不等）。是否有任何好的贪婪实现来解决这个问题，还是我自己来实现这个？我不是 LP 方面的专家，但任何可以解决此问题的 LP 求解器（来自 numpy/scipy）也是可以接受的。

How to set decision variables types like binary, int, double in Apache Commons Math SimplexSolver? The output of the program below is this:

I want decision variables to be of type int not double; output should be 333, 0, 8325 if solved as integer decision variables.

简而言之，我们现在正在尝试将 IQP 更改为 ILP。旧的实现大约需要 2 天才能完成，现在使用线性工具——它应该会加快速度。基本上问题是最大化（大约 50 个二进制变量）：

$$\sum_{g=1}^{5}sum_{p=1}^{10} ( S[p]x[g][p]-疲倦[g][p]-睡眠[g][p ])$$

更新

我认为 David 走在正确的轨道上，但是当我尝试使用奖励变量最大化表达式时，它们每次都为零，为什么？在一些代码下面，分数可能像S[1..10]=[1,2,3,4,5,6,7,8,9,10];.

我的问题是关于一个古老的运输问题——用一艘船一次只能运送一件物品，带着三件物品过河。一个约束是某些项目不能放在一起，例如卷心菜和山羊，狼和山羊等。这个问题应该可以使用整数规划或其他优化方法来解决。成本函数是河对岸的所有项目，到达那里所需的行程可能是 Simplex (?) 的输出，它尝试了不同的可行解决方案。我想知道是否有人有这个问题的整数规划（或线性规划）公式，和/或基于 Matlab、Octave、Python 的代码可以以编程方式提供解决方案，包括尝试所有路径的 Simplex 的踪迹——我们的乘船游览.

这里有一些有趣的东西

http://www.zib.de/Publications/Reports/SC-95-27.pdf

谢谢，

我有一个大规模的线性规划问题。我可以使用“linprog”在matlab中解决它。但是，它在一个循环内，我需要从第二次迭代绕过它到循环结束。这是一个简单的LP，形式如下：

最小化总和 a_i b_i st。...

其中 a_is 是我的变量， b_is 是系数​​。在每次循环迭代中，只有 b_is 略有变化。在此更改后，我想要变量的新值。（请注意，matlab 对大规模问题不使用单纯形法）。

有什么办法可以节省我在循环中的时间并且不多次解决 LP 问题？

谢谢

我正在尝试解决一个问题，即有一组对象需要在特定时间在各个点之间移动。

我已经能够在线性规划方面形式化大多数约束，即：

对于所有对象及其所有到达/离开，依此类推。目标函数将是在运输中花费最少或最多的时间。

我遇到的问题是一个额外的限制：某些物体在旅行期间需要由其他物体陪伴。例如，object1 可以伴随 object2、object3 或 object4。这些对象本身具有一定的到达或离开限制。我想让我的（也许是混合整数）线性程序负责拾取伴随的对象。但是在尝试将其形式化时，我无法找到一种保持线性的方法。我想到了混合整数约束，例如

但我不知道如何表达诸如“如果对象 2 伴随对象 1，它将在时间 X 与对象 1 离开并在时间 Y 到达”之类的约束。这似乎是非线性的，因为我会将布尔变量（如果对象 2 伴随对象 1）乘以旅行时间。

当然，我可以为每个“if...then...”语句创建不同的线性问题，但是有 60 个伴随路径和 10 个伴随对象，这将导致 10^60 个线性程序要解决，这不是好的。

如果有人对如何形式化这个线性规划问题有任何直觉，以便做出“X 会伴随 Y”的决定吗？可以用问题本身来表达，我将不胜感激！

我正在尝试使用 R 来解决加权顶点覆盖问题的一个实例，但我似乎无法正确解决。我正在使用ROI包（也可以使用linprog）。

该实例如下所示：

我的代码是：

结果是No solution found.我不知道我做错了什么，但它也可能是显而易见的。无法理解它——一个解决方案应该总是存在的，即使它需要所有的顶点（即所有变量都> = 0.5）。

如果重要的话，我在 Arch Linux 上从存储库（版本 2.14）运行 R 并通过install.packages("...").

谢谢！

我目前使用 BLEIC 进行最小化解决方案。我在以下链接http://msdn.microsoft.com/en-us/library/ff628587%28v=vs.93%29.aspx中实现了 MSDN 示例中的一个案例

以下是我的源代码。

我的问题是，当我设置不同的初始点时，我得到不同的答案，有时会返回“NAN”案例 1：设置初始点，real_1d_array x = “[3000.0,4500.0]”，返回正确答案 [2000, 3500] 案例 2：设置 real_1d_array x = "[1000.0,1000.0]"，返回 [NAN, NAN]

问题是由什么引起的？以及如何解决？

我正在为k-Minimum Spanning Tree 问题寻找整数 LP 形式化。

我的点子：

• x_ij = 1 表示树中有一条从 i 到 j 的边。
• y_i = 1 表示顶点 i 是树的一部分
• c_ij 是从 i 到 j 的边的成本

目标函数：所有 i,j 的 min sum(x_ij*c_ij)

约束：

1. 总和 y_i = k (1)
2. sum(x_ij) 对所有 j 和一些 i >= yi (2)
3. 所有 j 和一些 i >= yi (3) 的 sum(x_ji)
4. 2*x_ij <= yi+yj

(1) 确保 MST 中恰好有 k 个顶点。(2) 和 (3) 确保如果节点 i 在树中，则至少包含该节点的一条边在树中。(4) 表示如果树中 i 和 j 之间有一条边，那么顶点 i 和 j 也必须在树中。

不幸的是，这并没有按预期工作。有人知道我的错误吗？