Reputation: 1980
I've got a problem where I need to optimize the allocation of some products. Each product has a weight (basically how much the client likes it), and a category (some clients don't accept every product)
my data look something like this
prod_name, category, weight
name1, c1, 10
name2, c1, 5
name3, c1, 1
name4, c2, 8
name5, c2, 7
name6, c2, 6
and I have another table saying that we have debt in different categories (the same categories as the above table)
category, debt
c1, 100
c2, 500
I want to maximize X*weight (which in this case would be the dot product of two six-dimensional vectors), under the constraint that x1 + x2 + x3 = 100
, (alternatively, think of it as saying the variables corresponding to category 1 must add up to the debt in category one) and x4 + x5 + x6 = 500
in reality, I have like 800 categories, so I want to do it programatically, but I have no idea how to start building this problem.
The objective is easy enough
Xxx = cvx.Variable(len(R))
objective = cvx.Maximize(cvx.sum_entries(Xxx.T*R))
Where R is just the 'weight' column as a numpy array
But I can't figure out how to build the contstraints. Also, I want to keep track of the names (that is, once I get a solution, I need to map all the elements of the solution array back to the names in the prod_name column)
Does cvxpy allow either of these things, or do I need to look at other packages?
Upvotes: 1
Views: 709
Reputation: 61567
The following should accomplish your goal, as I understand it. Note that the solution seems trivially easy: just maximize the number of heavily-weighted items to meet the debt, regardless of the alternatives.
#!/usr/bin/env python3
import cvxpy
#The data from your original post
weights = [
{"name":'name1', "cat":'c1', "weight":10},
{"name":'name2', "cat":'c1', "weight": 5},
{"name":'name3', "cat":'c1', "weight": 1},
{"name":'name4', "cat":'c2', "weight": 8},
{"name":'name5', "cat":'c2', "weight": 7},
{"name":'name6', "cat":'c2', "weight": 6}
]
#The data from your original post
debts = [
{"cat": 'c1', "debt": 100},
{"cat": 'c2', "debt": 500}
]
#Add a variable to each item in weights
for w in weights:
w['var'] = cvxpy.Variable()
#Add up all the weight variables from each category
weights_summed_by_cat = dict()
for w in weights:
if w['cat'] in weights_summed_by_cat:
weights_summed_by_cat[w['cat']] += w['var']
else:
weights_summed_by_cat[w['cat']] = w['var']
#Create a list of debt constraints from the summed weight variables
constraints = []
for d in debts:
if d['cat'] in weights_summed_by_cat:
constraints.append(weights_summed_by_cat[d['cat']]<=d['debt'])
#Don't allocate negative amounts
for w in weights:
constraints.append(w['var']>=0)
#Create the objective function
obj = cvxpy.Maximize(cvxpy.sum([w['weight']*w['var'] for w in weights]))
#Create a problem instance
prob = cvxpy.Problem(obj, constraints)
#Solve the problem and catch the optimal value of the objective
val = prob.solve()
#Print optimal value
print("Final value: {0}".format(val))
#Print the amount assigned to each weight
for w in weights:
print("Allocate {0} of {1}".format(w['var'].value, w['name']))
Upvotes: 1