使用来自多组选项的约束最小化优化

Question

我正在寻找一种方法，通过从每个组都包含选项的大型数据集中为每个组选择一个选项来最小化具有多个约束的成本。该数据集由大约 100 个组组成，每个组有 200 个选项。

下面列出了优化条件、数据示例以及结果应该是什么。在小型数据集上，我只是遍历了所有组合，但对于实际的大型数据集，这将需要很长时间。我查看了 SciPy Optimize Minimize 但这似乎不合适。是否存在可用于找到最低成本的现有优化框架？如果没有，在Python中有什么好的解决方法？

条件

每组只有一个选项
最小化成本总和
A 的总和必须小于 10
B 的总和必须小于 12

数据集

+-------+--------+-----+-----+-------+
| Group | Option |  A  |  B  | Costs |
+-------+--------+-----+-----+-------+
|     1 |      1 |  10 |   0 |    10 |
|     1 |      2 |   0 |   0 |    21 |
|     1 |      3 |   0 |   7 |    15 |
|     2 |      1 |   8 |   0 |     8 |
|     2 |      2 |   0 |   0 |    34 |
|     2 |      3 |   0 |   5 |    18 |
|     3 |      1 |   9 |   0 |     9 |
|     3 |      2 |   0 |   0 |    20 |
|     3 |      3 |   0 |   6 |     7 |
+-------+--------+-----+-----+-------+

结果

+-------+--------+
| Group | Option |
+-------+--------+
|     1 |      1 |
|     2 |      3 |
|     3 |      3 |
+-------+--------+
Total costs: 35
Sum A: 10
Sum B: 11

Answer 1

这是一个使用 CVXPY (http://www.cvxpy.org/en/latest/index.html) 的解决方案。我安排了数据，使得 A、B、成本是矩阵，列 i 代表组 i.

的选项

import cvxpy as cvx
import numpy as np

A = np.array([[10,8,9],[0,0,0],[0,0,0]])
B = np.array([[0,0,0],[0,0,0],[7,5,6]]) 
cost = np.array([[10,21,15],[8,34,18],[9,20,7]]).T

choices = cvx.Int(3,3)
constraints = [cvx.sum_entries(choices[:,i]) == 1 for i in range(3)] + [cvx.sum_entries(cvx.mul_elemwise(A,choices)) <= 10] + [cvx.sum_entries(cvx.mul_elemwise(B,choices)) <= 12] + [choices >= 0, choices <= 1]
objective = cvx.Minimize(cvx.sum_entries(cvx.mul_elemwise(cost,choices)))
prob = cvx.Problem(objective,constraints)
prob.solve()

print(int(round(prob.value)))
print(np.matrix(prob.variables()[0].value.round(),dtype = np.int))

出于某种原因，输出值仍然是浮点数，所以我将它们转换回整数。

使用来自多组选项的约束最小化优化

Minimize optimization with constraints from multiple sets of options

python

optimization

constraints

minimization