CODEWITHSUNDEEP
mathematical-optimizationlinear-programmingcvxpy
Mohammad Athar
Mohammad Athar

Reputation: 1980

cvxpy, linear optimization, programatically build problem with objective being a sum of a few variables

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

Answers (1)

Richard
Richard

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

Related Questions