Python 中的优化问题（使用二进制数组）可能的解决方案

Question

我有一个大二进制 numpy 数组 (1000,2000)。总体思路是数组的列代表从 0 到 2000 的时间，每一行代表一个任务。数组中每个0代表失败，每个1代表成功。

我需要做的是 select 1000 个可用任务中的 150 个（行轴），并最大化唯一列的总成功数（1 秒）。它不一定是连续的，我们只是希望每个时间段的成功率最大化（只需要 1 次成功，任何额外的都是无关紧要的）。我要 select 最好的“篮子” 150 个任务。子数组行可以取自 1000 个初始行的任何位置。我想要 150 个任务的最佳“篮子”，这些任务会导致跨时间（列）取得最大成功。（为更加清晰而编辑）

数组的真实基本示例：

array([[0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0],
       [0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
       [0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0],
       [1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0],
       [1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
       [1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0]])

我已经成功创建了一个 Monte Carlo 模拟，使用 NumPy 中随机生成的任务篮，然后遍历数组并求和。正如您可以想象的那样，这需要一段时间，并且考虑到大量的潜在组合，它是低效的。有人可以指出一种算法或方法来在像 PuLP 这样的求解器中解决这个问题吗？

Answer 1

为什么不只计算每一行的成功总和，然后您就可以轻松地选择前 150 个值。

Answer 2

试试这个：

n = 150
row_sums = np.sum(x, axis=1)
top_n_row_sums = np.argsort(row_sums)[-n:]
max_successes = x[top_n_row_sums]

这会获取每一行的总和，获取最高 n 总和的索引，并使用这些行索引索引到 x。

请注意，行最终将按各列总和的升序排序。如果您希望行按正常顺序排列（按索引升序排列），请改用：

max_successes = x[sorted(top_n_row_sums)]

Python 中的优化问题（使用二进制数组）可能的解决方案

Optimization Problem in Python (using binary array) possible solutions

python

numpy

python-3.x

pulp