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

Question

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?

we treat X as continuous, but if it makes the problem easier, then I can cast it to an integer (it's a dollar value) — Mohammad Athar
– Mohammad Athar, Commented Oct 30, 2018 at 17:41
If X were integer-valued that would actually make the problem much harder (NP-complete rather than the polynomial time which is possible for linear programming). — Richard
– Richard, Commented Oct 30, 2018 at 20:30

Richard · Accepted Answer · 2018-10-30 20:28:45Z

1

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']))

answered Oct 30, 2018 at 20:28

Richard

62.7k40 gold badges198 silver badges277 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Mohammad Athar Over a year ago

Thanks! maximizing the number of heavily weighted items only works if we have unlimited inventory; I'm adding constraints one at a time and didn't include inventory in this problem statement.

Mohammad Athar Over a year ago

also, w['var'] gives me a key error, since var is not a key in the dictionary w

Richard Over a year ago

@Mohammad: I have a for loop that creates that key. You'll have to be more specific about what your problem is. (Are you in Python 3?)

Collectives™ on Stack Overflow

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

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related