问题标签 [linear-programming]

有什么好的工具可以解决 Linux 上的整数程序吗？

我有一个小问题要计算以节省时间：D。这是一种子集和问题。我有一个大约 20 个整数值的列表，我想计算满足某个最小值的最小总和的子集。你可以用一个整数程序来制定这个......就像

和

还是有其他好方法可以做到这一点？

我需要建立一个线性规划模型。这是我正在使用的不等式（例如）：

我需要找到这些不等式所描述的区域，并在图形中对其进行着色，并跟踪该区域边界线的顶点，并以不同的颜色绘制边界线。有关我正在寻找的示例，请参见下图。

.

我正在使用 Python 3.2、numpy 和 matplotlib。Python中有更好的线性编程模块吗？

我不确定这是否真的是一个“着色”问题，就像它是一个分配/线性规划问题一样。我在这两个方面的专业知识都为零，所以请原谅可能出现的任何菜鸟。但我觉得这个问题之前几乎肯定已经解决/调查过，在查看http://en.wikipedia.org/wiki/Category:Graph_algorithms上的许多图形算法后，我找不到任何东西。我希望能在正确的方向上得到一些指示。

“问题陈述”有效地归结为：

1. 图中有两种类型的顶点：路由器和核心。

2. 核心仅连接到路由器。每个核心仅连接到单个路由器。每个都有用户输入/定义的“颜色”。（在我的具体问题中，颜色仅限于说 4/5 可能的颜色之一）。它们的颜色不能改变，它是一个输入参数。（核心是下图中的正方形）

3. 路由器连接到核心以及其他路由器。他们没有分配给他们的“颜色”。分配颜色是程序/算法目标的一部分。（路由器是下图中的圆形顶点。）

4. 该程序的目标是为图中的每个路由器分配颜色，以使不同颜色的顶点之间的“交叉”/边的数量最小化。

（另一种观点：本质上，您会得到一个图，其中一些顶点是彩色的，而另一些则不是。目标是对那些没有着色的顶点着色，以使不同颜色的顶点之间的边数最小化。）

我能够将这个（我确定很差）制定为一个整数线性程序，并使用 LP-Solve 设置了一个解决方案/方法。我也有自己的启发式方法。我很想知道解决这个问题的“正确”/已知/其他方法？！

非常感谢！

我正在尝试建立一个线性程序，其中目标函数将额外的权重添加到max决策变量乘以它们各自的系数。

考虑到这一点，有没有办法在线性规划的目标函数中使用min或max运算符？

例子：

请注意，这(c4 * max(c1*x1, c2*x2, c3*x3))是我关心的“额外重量”术语。我们让c4表示“额外权重”系数。另请注意，在此特定示例中x1，x2、 和x3是整数。

我认为以上内容可能超出了线性编程提供的范围。但是，也许有一种方法可以将其破解/重新格式化为有效的线性程序？

如果这个问题完全超出了线性规划的范围，也许有人可以推荐一个更适合这类问题的优化范式？（任何能让我避免手动枚举和检查所有可能的解决方案的方法都会有所帮助。）

我有一个集合 I ={P1, P2, ..., Pm} 和 I 的 n 个有限子集，用 R1,R2,...,Rn 表示，如下所示：

R1 = {P1, P2}

R2 = {P2, P4}

R3 = {P2，P3，P4}

R4 = {P1，P2，P4}

……

其中 Pi 表示一个整数。

对于每个 Ri，我想计算其所有元素的乘积。我的目标是通过在 Ri (i=1,2,...,n) 之间共享一些公共部分来尽可能少地使用乘法和除法。

例如，如果我可以先计算 P2*P4，那么这个结果可以用于计算 R3 和 R4 的所有元素的乘积。

请注意，也允许除法。例如，我可以先计算 A=P1*P2*P3*P4，然后使用 A/P1 计算 R3 的所有元素的乘积，然后使用 A/P3 计算 R4。

如果我想使用最小乘法和除法来计算 I 的每个子集的所有产品，这是一个集合覆盖问题吗？NP完全？顺便说一句，您能否给出一个整数线性程序公式来描述它，就像这里一样。

任何建议将不胜感激！

社区编辑：附加假设：

• 允许除法，与乘法相同的成本
• 给定集合中没有重复的元素。例如R5 = {P1, P1, P1, P2}不允许

我有 3 个集合 A、B 和 C，每个集合有 n 个元素。这些集合可以包含重复项（不确定 Set 是否正确）。

现在我试图用 n 个元素（比如 D1 到 Dn）形成一个集合 D，每个元素 Di 包含 3 个元素，一个来自 A，一个来自 B，一个来自 C。

我的目标是找到最小化 Di 中元素乘积之和的集合 D。

蛮力在这里似乎是一个非常糟糕的主意，因为即使对于 n>5，算法的速度也会非常慢。任何人都可以提出更好的方法吗？线性规划适合这个问题吗？

我有以下代码：

在哪里：

Demand当它应该是一个向量时，它似乎是一个矩阵。如何将其转换为向量并将相同的元素保留在相同的“位置”？

另外，矩阵连接是最好的方法吗？我正在尝试为整个数据集找到最佳x1值x2。

嗨，我有以下用于 linprog 优化的代码。

其中 WT_output 和 PV_output 是 3 维 365x24 数组，Demand 是 365x24

我正在尝试为 Demand 的每个 365x24 元素和每个维度优化 x1 和 x2，以便找到最佳的 K 和 M 组合

但是，就目前的代码而言，我不断收到错误消息-“A 中的行数必须与 b 的元素数相同。”

有没有人有什么建议？

嗨，我有以下使用 linprog 的代码

其中 PV = 8760x2，WT = 8760 x 2 和 x = 2x1。当我运行这个程序时，优化会以退出标志 1 收敛，但我要么得到 x1 =0 的值，要么得到等于某个整数的 x2 值。

为什么输出不给出混合结果（即 x1 和 x2 的非零值？

“下标分配尺寸不匹配。' 运行 linprog 编码时。

我的代码是

PV_output 为 8760x1x27，WT_output 为 8760x1x3

我试图在此代码中为 27 和 3 PV 和 WT 的所有组合找到下面的“f”系数有谁知道如何索引“f”来做到这一点？

谢谢