Python 背包问题——使用所选物品的平均值作为约束条件？

Question

我对 python 还是比较陌生，所以我不知道如何完成某项壮举。

我想做什么：我有一个包含两列的 Excel 文件 - 卖出和保证金。可能有可变数量的行。我需要找到一个“最适合”，其中 n# 的销售行的总和在目标销售量的 5% 以内并且平均保证金也在目标保证金 % 的 5% 以内（如果有解决方案，如果不再增加 % 公差和运行。但我可以稍后解决）。

通过谷歌搜索，我了解到这是一个多约束背包问题，并且能够找到一些示例来解决。我借用的代码来自这里：https://towardsdatascience.com/solving-the-multiple-knapsack-problem-with-google-or-tools-e961dfc8288e

我的问题：我不知道如何设置一个约束条件，使放入包中的物品的平均边距接近目标平均边距。

这是我在上面的网站上修改后的代码，我在其中使用随机数据进行销售和保证金：

from ortools.linear_solver import pywraplp

solver = solver = pywraplp.Solver.CreateSolver('SCIP')

data = {}
sell = [8520,9600,5340,8379,846,1098,1510,4954,1039,620,795,3260,75,200,75]
margin = [25, 25, 25, 34, 25, 25, 25, 25, 25, 25, 27, 20, 100, 27, 100]

assert len(sell) == len(margin)
data['values'] = values
data['sell'] = sell
data['margin'] = margin
data['items'] = list(range(len(sell)))
data['num_items'] = len(sell)
number_bags = 1 #All have the same capacity of 50 pounds
data['target_amount'] = [9262]
data['avg_margin'] = [27] 
data['bags'] = list(range(number_bags))
assert len(data['target_amount']) == number_bags
assert len(data['target_amount']) == len(data['avg_margin'])
print('sell:',*data['sell'])
print('margin:',*data['margin'])
print("Number of Items:", data['num_items'])
print("Number of Knapsacks:" , number_bags)

x = {}
for i in data['items']:
    for j in data['bags']:
        x[(i,j)] = solver.IntVar(0,1,'x_%i_%i' % (i, j))

#Constraint for an item being placed in 1 knapsack
for i in data['items']:
    solver.Add(sum(x[i,j] for j in data['bags'])<=1)
    
#Knapsack Capacity Constraint
for j in data['bags']:
    solver.Add(sum(x[(i,j)]*data['sell'][i] 
                  for i in data['items']) <= data['target_amount'][j])
#margin Constraint
#for j in data['bags']:
#    solver.Add(sum(x[(i,j)]*data['margin'][i]
#                  for i in data['items']) <= data['target_amount'][j])

#objective function
objective = solver.Objective()
for i in data['items']:
    for j in data['bags']:
        objective.SetCoefficient(x[(i,j)], data['sell'][i])
objective.SetMaximization()

solv = solver.Solve()
if solv == pywraplp.Solver.OPTIMAL:
    print('Total Packed Value:', objective.Value())
    total_Sell = 0
    for j in data['bags']:
        bag_Sell = 0
        avg_margin= 0
        count = 0
        print('\n','Bag', j+1 , '\n')
        for i in data['items']:
            if x[i,j].solution_value()>0:
                print('Line:', i , 
                      'Sell', data['sell'][i], 
                      'margin',data['margin'][i],
                     )
                bag_Sell += data['sell'][i]
                avg_margin += data['margin'][i]
                count += 1
        print('Packed Knapsack Sell: ', bag_Sell)
        print('Packed Knapsack margin: ', round(avg_margin / count, 2))
else:
    print("There is no optimal solution")


Is this even possible? Am I just way out of my league?

Thanks

Answer 1

使用数学（和一张纸）通常比使用代码更好。所以我们有：

 sum(i,x[i]*m[i])
 ---------------- ≈ Target
   sum(i,x[i])

第一步是去掉除法：

 sum(i,x[i]*m[i]) ≈ Target * sum(i,x[i])

或者

 |sum(i,x[i]*m[i]) - Target * sum(i,x[i])| <= MaxDeviation

这可以线性化为：

 -MaxDeviation <= sum(i,x[i]*m[i]) - Target * sum(i,x[i]) <= MaxDeviation

Answer 2

添加平均边距约束不是很困难，一旦你写下来。

将平均边距保持在两个范围内的约束

您可以在模型中添加以下内容：

min_acceptable_margin = data['target_margin'][0] * 0.95
max_acceptable_margin = data['target_margin'][0] * 1.05

#Average Margin Constraints
for j in data['bags']:
   solver.Add(sum(x[(i,j)]*data['margin'][i] - x[(i,j)] * min_acceptable_margin
                 for i in data['items']) >= 0 , name=f"GT_Target_Avg")
   solver.Add(sum(x[(i,j)]*data['margin'][i] - x[(i,j)] * max_acceptable_margin
                 for i in data['items']) <= 0 , name=f"LT_Target_Avg")

如您所见，我们在 LP 中写出了保持约束线性的条款。

既然你说你是Python的新手，我提供完整的代码：

完整工作代码（OR-Tools LP）

from ortools.linear_solver import pywraplp
solver = solver = pywraplp.Solver.CreateSolver('SCIP')

sell = [8520,9600,5340,8379,846,1098,1510,4954,1039,620,795,3260,75,200,75]
margin = [25, 25, 25, 34, 25, 25, 25, 25, 25, 25, 27, 20, 100, 27, 100]
target_margin = [40]
bag_capacities = [9262]


def prepare_data():
  data = {}
  assert len(sell) == len(margin)
  data['sell'] = sell
  data['margin'] = margin
  data['items'] = list(range(len(sell)))
  data['num_items'] = len(sell)
  number_bags = 1 
  data['target_amount'] = bag_capacities
  data['target_margin'] = target_margin
  data['bags'] = list(range(number_bags))
  assert len(data['target_amount']) == number_bags
  assert len(data['target_amount']) == len(data['target_margin'])
  print('sell:',*data['sell'])
  print('margin:',*data['margin'])
  print("Number of Items:", data['num_items'])
  print("Number of Knapsacks:" , number_bags)

  return data


data = prepare_data()
print(data)


#Start Formulating the problem
x = {}
for i in data['items']:
    for j in data['bags']:
        x[(i,j)] = solver.IntVar(0,1,'x_%i_%i' % (i, j))

#Constraint for an item being placed in 1 knapsack
for i in data['items']:
    solver.Add(sum(x[i,j] for j in data['bags'])<=1, name="Max_One_Item"+str(i))

#Knapsack Capacity Constraint
for j in data['bags']:
    solver.Add(sum(x[(i,j)]*data['sell'][i] 
                  for i in data['items']) <= data['target_amount'][j], name=f"BagCapacity_{i}")

#Average Margin Constraints
min_acceptable_margin = data['target_margin'][0] * 0.95
max_acceptable_margin = data['target_margin'][0] * 1.05

for j in data['bags']:
   solver.Add(sum(x[(i,j)]*data['margin'][i] - x[(i,j)] * min_acceptable_margin
                 for i in data['items']) >= 0 , name=f"GT_Target_Avg")
   solver.Add(sum(x[(i,j)]*data['margin'][i] - x[(i,j)] * max_acceptable_margin
                 for i in data['items']) <= 0 , name=f"LT_Target_Avg")

#objective function
objective = solver.Objective()
for i in data['items']:
    for j in data['bags']:
        objective.SetCoefficient(x[(i,j)], data['sell'][i])
objective.SetMaximization()

#Call the solver
solv = solver.Solve()

#Print the results
if solv == pywraplp.Solver.OPTIMAL:
    print('Total Packed Value:', objective.Value())
    total_Sell = 0
    for j in data['bags']:
        bag_Sell = 0
        avg_margin= 0
        count = 0
        print('\n','Bag', j+1 , '\n')
        for i in data['items']:
            if x[i,j].solution_value()>0:
                print('Selected:', i , 
                      'Sell', data['sell'][i], 
                      'margin',data['margin'][i],
                     )
                bag_Sell += data['sell'][i]
                avg_margin += data['margin'][i]
                count += 1
        print('Packed Knapsack Sell: ', bag_Sell)
        print('Avg Packed Knapsack margin: ', round(avg_margin / count, 2))
        print(f'Target Margin {data["target_margin"][0]} (Min {min_acceptable_margin} Max {max_acceptable_margin})')
else:
    print("There is no optimal solution")

当我用上面的数字运行时，我得到了以下结果：

Total Packed Value: 9109.0

 Bag 1 

Selected: 7 Sell 4954 margin 25

Selected: 9 Sell 620 margin 25
Selected: 11 Sell 3260 margin 20
Selected: 12 Sell 75 margin 100
Selected: 13 Sell 200 margin 27
Packed Knapsack Sell:  9109
Avg Packed Knapsack margin:  39.4
Target Margin 40 (Min 38.0 Max 42.0)

调试时的有用命令

一些方便的命令可以帮助您调试 LP：

print('Number of variables =', solver.NumVariables())

print('Number of constraints =', solver.NumConstraints())

最后，最后一个非常有用的技巧。把求解器看到的公式写出来就好了。

#Use this to print out the ORTOOLS Formulation
print(solver.ExportModelAsLpFormat(False).replace('\', '').replace(',_', ','), sep='\n')

希望能帮助您前进。

Python 背包问题——使用所选物品的平均值作为约束条件？

Python Knapsack problem - using the average value of the selected items as a constraint?

python

knapsack-problem

linear-programming

完整工作代码（OR-Tools LP）