Python中的约束优化求解器

Question

我需要帮助将我的问题表述为Python中的约束优化问题。在

假设我有一个PandasDataFrame的视频，这些视频包含以下列

id, views, score

1. id是每个视频的唯一标识
2. views是视频的观看次数
3. score是计算视频质量分数的函数f的输出。它的实施对于这个问题并不重要。在

我现在有两个独立但相关的优化功能，我想实现

1. 给定最大数量的视频C，最小的总浏览量V找到一组平均得分最大的视频。在
2. 给定最大数量的视频C和最低质量分数Q找到使总浏览量最大化的视频集。在

例如，假设以下数据

+----+-------+-------+
| ID | Views | Score |
+----+-------+-------+
| X  |     1 |   0.9 |
| Y  |     2 |   0.8 |
| Z  |     3 |   0.7 |
+----+-------+-------+

如果我们使用约束条件进行上述优化1，下表将总结不同标准的结果：

^{pr2}$

如果我们在上面的约束条件下进行优化2，下表将总结不同标准的结果：

+-------------+----------------+------------------+
| C Less Than | Q Greater Than | Resultant Videos |
+-------------+----------------+------------------+
|           3 |           0.85 | X                |
|           3 |           0.75 | X, Y             |
|           3 |           0.95 | No Solution      |
+-------------+----------------+------------------+

我觉得答案就在scipy的optimize库中。应该注意这是一个0-1 knapsack problem and not a fractional knapsack problem。在

谢谢

Answer 1

你的问题似乎没有很好地表达出来。就线性规划（优化）而言，你可以将其表述为

\max b_1 \sum_i c_i/N+b_2 \sum_i v_i

such that \alpha c\geq \bar{c}
          \beta v\leq \underline{v}
          \gamma q\leq \underline{q}

对于固定标量b_1、b_2、N和向量α、β、γ。在

在第一行中，您可以同时最大化平均得分c_i和视图总数v_i

现在，您可以使用scipy的优化来解决这个问题。在

注：很抱歉格式化，我对堆栈交换很陌生