桶约束优化

Question

我试图设计一个基于优化元素组/桶的约束，而不仅仅是单个元素。以下是我所有约束的列表:

1. 所有元素的总和必须等于某个值
2. 每个产品的总和(元素的列和)必须等于某个值
3. 大小为'x'的桶，其中桶中的每个元素必须相同

下面是我想要的一个例子:

Total Budget = 10000
Product-A Budget = 2500
Product-B Budget = 7500
Product-A Bucket Size = 3
Product-B Bucket Size = 2

Below is an illustration of the buckets (have placed them randomly, optimizer should decide where to best place the bucket within each column):
Product-A   Product-B 
_______                 
Week 1  |       |             
Week 2  |       |    ________ 
Week 3  |_______|   |        |
Week 4              |________|
Week 5                        

将约束传递给优化器后，我希望优化器像这样分配元素(bucket内的每个元素都应该相等):

期望的优化器输出

Product-A   Product-B 
_______                 
Week 1  |  500  |      150    
Week 2  |  500  |    __2350__ 
Week 3  |__500__|   |  1000  |
Week 4     700      |__1000__|
Week 5     300         3000    

下面是我创建bucket约束的尝试。为了演示，我使用了一个简单的虚拟目标函数:

# Import Libraries
import pandas as pd
import numpy as np
import scipy.optimize as so
import random
# Define Objective function (Maximization)
def obj_func(matrix):
return -np.sum(matrix)

# Create optimizer function
def optimizer_result(tot_budget, col_budget_list, bucket_size_list):
# Create constraint 1) - total matrix sum range
constraints_list = [{'type': 'eq', 'fun': lambda x: np.sum(x) - tot_budget},
{'type': 'eq', 'fun': lambda x: (sum(x[i] for i in range(0, 10, 5)) - col_budget_list[0])},
{'type': 'eq', 'fun': lambda x: (sum(x[i] for i in range(1, 10, 5)) - col_budget_list[1])},
{'type': 'eq', 'fun': lambda x, bucket_size_list[0]: [item for item in x for i in range(bucket_size_list[0])]},
{'type': 'eq', 'fun': lambda x, bucket_size_list[1]: [item for item in x for i in range(bucket_size_list[1])]}]
# Create an inital matrix
start_matrix = [random.randint(0, 3) for i in range(0, 10)]
# Run optimizer
optimizer_solution = so.minimize(obj_func, start_matrix, method='SLSQP', bounds=[(0, tot_budget)] * 10,
tol=0.01,
options={'disp': True, 'maxiter': 100}, constraints=constraints_list)
return optimizer_solution

# Initalise constraints
tot_budget = 10000
col_budget_list = [2500, 7500]
bucket_size_list = [3, 2]

# Run Optimizer
y = optimizer_result(tot_budget, col_budget_list, bucket_size_list)
print(y)

Answer 1

我不确定你是否真的想最大化这里的东西，或者如果你只是想找到任何可行的解决方案，满足你所有的约束。在这个答案中，我将假设是后者，但在下面的模型中包含一个目标函数是很直接的。

首先，您将需要二进制变量来建模决定同一桶中的哪些元素必须具有相同的值，因此您的问题变成了混合整数线性优化问题(MILP)。由于存储桶需要是连续的，所以可以很容易地计算出所有可能的存储桶间隔。这意味着你的优化模型只需要决定这些区间中哪一个是最好的。

还值得一提的是，scipy.optimize.minimize默认情况下不支持整数变量(您可以尝试一些惩罚方法，但我猜这超出了这个答案的范围)。这就是为什么你需要一个建模库，如python-mip, pyomo或PuLP来建模你的问题，并将其传递给MILP求解器。

这里有一个通过PuLP包的解决方案:

from pulp import LpProblem, LpVariable

# parameters
weeks = [1, 2, 3, 4, 5]
products = ["A", "B"]
total_budget = 10_000
col_budgets = {"A": 2500, "B": 7500}
bucket_sizes = {"A": 3, "B" : 2}
bucket_intervals= {
"A": {0: [1, 2, 3], 1: [2, 3, 4], 2: [3, 4, 5]},
"B": {0: [1, 2], 1: [2, 3], 2: [3, 4], 3: [4, 5]}
}
# create the model
mdl = LpProblem()
# x[i, j] is the (contiguous and positive) value of product i at week j
x = {(i, j) : LpVariable(name=f"x[{i},{j}]", cat="Continuous", lowBound=0.0) for i in products for j in weeks}
# b[i, k] = 1 if product i is placed inside the k-th possible bucket interval, 0 otherwise
b = {(i, k) : LpVariable(name=f"b[{i},{k}]", cat="Binary") for i in products for k in bucket_intervals[i].keys()}
# total sum of all elements must equal a certain value
mdl.addConstraint(sum(x[i, j] for i in products for j in weeks) == total_budget)
# total sum of each product must equal a certain value
for i in products:
mdl.addConstraint(sum(x[i, j] for j in weeks) == col_budgets[i])
# we can only choose exactly one interval for the bucket of product i
for i in products:
mdl.addConstraint(sum(b[i, k] for k in bucket_intervals[i].keys()) == 1)
# Every element in the bucket must be the same
# If b[i, k] == 1, then all x[i, t] (with t in bucket_intervals[i][k]) have the same value 
for i in products:
for k in bucket_intervals[i].keys():
for t in bucket_intervals[i][k][:-1]:
# b[i, k] == 1 ---> x[i, t] == x[i, t + 1]
bigM = total_budget 
mdl.addConstraint(0 - bigM * (1 - b[i, k]) <= x[i, t] - x[i, t + 1])
mdl.addConstraint(0 + bigM * (1 - b[i, k]) >= x[i, t] - x[i, t + 1])
mdl.solve()
# print solution
for i in products:
for j in weeks:
val = x[i, j].varValue
print(f"x[{i},{j}] = {val}")

得到

x[A,1] = 833.33333
x[A,2] = 833.33333
x[A,3] = 833.33333
x[A,4] = 0.0
x[A,5] = 0.0
x[B,1] = 0.0
x[B,2] = 3750.0
x[B,3] = 3750.0
x[B,4] = 0.0
x[B,5] = 0.0