cvxpy, линейная оптимизация, программно построить задачу с целью, являющейся суммой нескольких переменных - PullRequest
Новая
       17

cvxpy, линейная оптимизация, программно построить задачу с целью, являющейся суммой нескольких переменных

0 голосов
/ 26 октября 2018

У меня есть проблема, когда мне нужно оптимизировать распределение некоторых продуктов. У каждого продукта есть вес (в основном, насколько клиенту это нравится) и категория (некоторые клиенты не принимают каждый продукт)

мои данные выглядят примерно так 

prod_name, category, weight
name1,     c1,    10
name2,     c1,    5
name3,     c1,    1
name4,     c2,    8
name5,     c2,    7
name6,     c2,    6

и у меня есть другая таблица, в которой говорится, что у нас есть долги в разных категориях (те же категории, что и в приведенной выше таблице) 

category, debt
c1,    100
c2,    500

Я хочу максимизировать вес X * (который в этом случае был бы точечным произведением двух шестимерных векторов) при ограничении, x1 + x2 + x3 = 100 (альтернативно, думайте об этом как о переменных, соответствующих категории 1 необходимо добавить в долг в первой категории) и x4 + x5 + x6 = 500

на самом деле у меня около 800 категорий, поэтому я хочу сделать это программно, но я не знаю, как начать строить эту проблему.

Цель достаточно проста 

Xxx = cvx.Variable(len(R))
objective = cvx.Maximize(cvx.sum_entries(Xxx.T*R))

Где R - просто столбец 'weight' в виде массива numy

Но я не могу понять, как построить ограничения. Кроме того, я хочу отслеживать имена (то есть, как только я получу решение, мне нужно сопоставить все элементы массива решений с именами в столбце prod_name)

Разрешает ли cvxpy что-либо из перечисленного или мне нужно взглянуть на другие пакеты?

1 Ответ

0 голосов
/ 30 октября 2018

Следующее должно выполнить вашу цель, насколько я понимаю.Обратите внимание, что решение кажется тривиально простым: просто максимизируйте количество тяжеловесных предметов для погашения долга, независимо от альтернатив. 

#!/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']))
...