问题标签 [discrete-optimization]

我有一个我认为是一个相当简单的约束满足问题，但找不到合适的包来实现算法。

我希望对一些点的数据集进行子集化。每个点都带有其他数据点的列表，如果要包含它，它必须从子集中排除。例如：

我想在不违反任何规则的情况下最大化我可以放入子集中的点数。我的数据包含 1000 点。为此类问题设置的算法名称是什么？它们是我应该看的 R 中的任何包吗？我应该看看其他编程语言吗？

给定一个分数矩阵，我想从每一列和每一行中准确地选择 n 个元素，以便整个矩阵中所选元素的总分尽可能高。

示例：给定成本矩阵

n=1 的最佳选择是：

该方案的总分是 0.65500799+0.87150676+0.99663978

n=2 的最佳选择是：

该方案的总得分为 0.65500799+0.53634974+0.79214695+0.87150676+0.99663978+0.80823699

这些解决方案是通过简单的广度优先搜索 (BFS)获得的。但是，对于较大的问题（例如，10x10，n=2），这种方法在计算上是不可行的（运行时间爆炸式增长）。

问题：

1. 这个离散优化问题是如何分类的？
2. 什么启发式方法可以快速找到解决这个问题的好方法？
3. 哪些 Python 库实现了这些启发式方法？

我试图找到一种（相对）快速的方法来最小化给定约束和界限的自然数集上的函数。我知道函数的数学形式及其约束，所以蛮力方法似乎很慢而且不是很优雅。解决这个问题的最佳方法是什么？

基本上，我试图从使用 scipy.optimize.minimize 对实数进行功能最小化到自然数上的一个。（我知道这要困难得多）

让事情变得容易。我在想这样的例子：

换句话说，我希望添加约束和界限

（我知道我可以通过从 xr 中排除这些值来强加它们，但这对于我所想到的实际情况来说似乎不太优雅且不太实用）

所以我期待有一些不同的最小化器，比如 scipy.optimize.basinhopping 或者神秘的东西来做这个把戏？有什么建议么？

是否有任何已知的算法可以使用最少数量的节点从一组集合中构建一棵树？

例如，我有以下集合：

每个集合都由从根到叶的路径表示。它们是集合，因此节点出现在路径中的顺序并不重要。

我需要一棵使用尽可能少的节点的树，它将所有给定的集合表示为路径。一种可能的解决方案（不确定是否最小）是：

其中根节点 0 是一些空元素。

我正在尝试用 python 解决订单最小化问题。因此，我将 M 个订单分配给 N 个工人。每个工人都有一个基本能量水平 X_i，它收集在向量 X 中。此外，每个订单都有一个特定的能量消耗 E_j，它收集在 E 中。话虽如此，我正在尝试解决以下问题

其中 Y 是某个最佳能级，范数为 2 范数。在约束条件下，任何一列加起来正好是一，因为订单应该完成并且只能由一名工人完成。我查看了 scipy.optimize 但据我所知，它似乎不支持这种优化。

有人知道 Python 中有什么工具可以解决这种离散优化问题吗？

我正在使用动态编程实现 0/1 背包问题。但是，当物品数量或麻袋容量太大时，我的算法无法完成，导致异常。这是一个简单的 DP 算法，它为项目编号创建一个 2D 矩阵。与容量。这是我的代码片段：

有什么想法可以提高执行时间吗？

我写作是因为我有一个离散的优化问题需要解决，而且我认为可能已经有一些理论结果，甚至是 Python 中实现它的库（例如来自 Google 的 OR-Tool）。

问题如下：我有使用不同模具打印的不同对象。你可以把物体想象成小士兵或其他任何东西。每种物体都有不同的模具。我总共有 3 台不同的打印机，其中 2 台可以（同时）使用 8 个模具，1 台可以使用 10 个模具。当不同对象的订单到达时，我必须打印所有对象以尽量减少打印数量。还有一个侧面约束，很重要，但不必直接进入问题的理论表述：每次换模具，都会有巨大的印刷材料损耗。因此，尽量减少模具更换次数甚至比尽量减少打印次数更重要（换句话说，最好打印比所需相同对象更多的次数，

这是一个可能有助于理解的示例：

• 订单：
  • 对象 A：80
  • 对象 B：95
  • 对象 C：101
  • ……
  • 对象 Z：71
• 模具：
  • 答：1
  • 乙：2
  • C: 3
  • ……
  • Z：1
• 可用的打印机（他们处理的模具数量）：
  • P1：8
  • P2：8
  • P3 10

注意：打印机总是需要装满模具。

我想了一个简单的算法来解决单个打印机的问题，利用每个对象的顺序/模具数量的比率，但我相信有更好的方法，甚至可以同时考虑多个“打印机”。在某种意义上，它类似于装箱问题，但它更复杂一些，条件更多。

对于“如何在 R 中运行此模型”问题，我深表歉意。当谈到统计模型时，我将是第一个承认我是新手的人。希望我有足够多的实质性问题来引起人们的兴趣，并且问题会更像是“R中的这个命令是否对应于这个统计模型？”

我正在尝试估计一个模型，该模型可以估计给定 Twitter 用户“关注”来自给定政党的政治用户的概率。我的数据框位于个人用户级别，每个用户都可以选择关注或不关注 Twitter 上的派对。作为替代特定变量，我测量了与 Twitter 用户和政党之间的意识形态距离，以及指定距离是正面还是负面的交互项。因此，在 Twitter 上关注政客的决定取决于你的意识形态距离。

最初我试图估计一个条件 logit 模型，但我很快就摆脱了这个想法，因为选择不是相互排斥的，即他们可以选择跟随多个政党。现在我怀疑我是否应该使用多项概率或多元概率，因为我希望我的模型允许个人选择多个替代方案。但是，当我尝试估计多项式概率时，我的代码不起作用。我的代码是：

我收到以下错误消息：

我已经尝试查找错误，但似乎找不到与概率模型相关的任何内容。你能告诉我我做错了什么吗？再次为我的无知感到抱歉。谢谢您的帮助。

另外，我尝试在下面的代码中复制我的数据框。该数据是针对第一个 Twitter 用户的前 6 个观察结果，但我有一个包含 5181 个用户的数据集，对应于 51810 个观察结果，因为丹麦有 10 个政党。

是否可以手动设置/调整分支和界限的悲观界限？

在我的情况下，我知道存在一个分数 = 0 的解决方案（但我还不知道解决方案本身，只知道分数并且它存在），所以我想使用这些高级知识来修剪搜索空间。

我想使用类似于 JPEG 压缩用于Y组件的某些步骤的图像处理算法。然而，我不想使用离散余弦变换scipy.fftpack.dct，在其中我们获得每个 x 和 y 组合矩阵的权重，然后我们使用量化规则进行量化，我想使用高斯作为基础而不是余弦函数.

该算法的预期结果将包括：

• 输入图像用一个小内核处理，它只查看总图像大小的一个子集（例如 9x9 像素）
• 内核由 x 和 y ( n x m) 的离散高斯组合组成（类似于用于 JPEG 压缩的 64 个余弦组合，但使用高斯）
• 内核获取子集数组并计算每个离散高斯组合的权重，并将权重作为n x m矩阵返回
• 然后我可以创建一个量化指标，将这个指标除以离散高斯组合矩阵，大多数组件将导致 0（取决于使用的指标阈值）。
• 这将允许我将我的图像压缩为每个图像子集的几个高斯分量。

从我有限的数学理解来看，这在数学上应该是可能的，因为用于内核的高斯函数可以在 x 和 y 轴上分解（这将加速处理，因为内核可以是线性的而不是立方的）。

问题：是否有任何算法/方法允许所有或部分描述的步骤（我使用 Python）？我不确定我在寻找什么术语。

谢谢！