Minimize optimization with constraints from multiple sets of options

Question

I am looking for a way to minimize costs with multiple constraints by selecting one option per group out of a large dataset with groups that each contain options. The dataset consists of around 100 groups with 200 options each.

Below is a list of the conditions for the optimization, an example of the data and what the result should be. On small datasets I just looped over all combinations but with the actual large dataset this would take forever. I looked into SciPy Optimize Minimize but that doesn't seem suitable. Is there an existing optimization framework that would be usable to find the lowest costs? If not, what would be a good way to solve it in Python?

Conditions

• Exactly one option per group
• Minimize sum of costs
• Sum of A must be lower than 10
• Sum of B must be lower than 12

Dataset

+-------+--------+-----+-----+-------+
| 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 |
+-------+--------+-----+-----+-------+

Result

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

Answer 1

Here is a solution using CVXPY (http://www.cvxpy.org/en/latest/index.html). I arranged the data such that A, B, cost are matrices and column i represents the options for group 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))

For some reason the output values are still float, so I cast them back to integer.