需要调整 scipy .linprog/.milp 的提示

Question

我的任务是优化产品成本，例如，找到不同容量和价格的油漆罐的最佳组合来为给定的正方形着色。

最简单的例子是：

pdict = {'Can_9ltr':[9, 0.17, 4870],
            'Can_4.5ltr':[4.5, 0.17, 2910],
            'Can_1ltr':[1, 0.17, 632],
            'Can_2.25ltr':[2.25, 0.17, 1790]}

其中列表[0]是特定罐的体积，列表[1]是每平方米的油漆消耗量，列表[2]是每罐的价格。

事实上，我使用纸浆库得到了一个完全有效的解决方案：

{'Target_value': 30,
 'Optimal_set': {'Can_1ltr': {'CPU': 632, 'Amount': 1.0, 'Cost': 632.0},
  'Can_2.25ltr': {'CPU': 1790, 'Amount': 0.0, 'Cost': 0.0},
  'Can_4.5ltr': {'CPU': 2910, 'Amount': 1.0, 'Cost': 2910.0},
  'Can_9ltr': {'CPU': 4870, 'Amount': 0.0, 'Cost': 0.0}},
 'Cost_total': 3542.0}

代码如下：

import pulp
import math

pdict = {'Can_9ltr':[9, 0.17, 4870],
            'Can_4.5ltr':[4.5, 0.17, 2910],
            'Can_1ltr':[1, 0.17, 632],
            'Can_2.25ltr':[2.25, 0.17, 1790]}
square = 30

def calculator(prod_dict, target_value):
    prods = list(prod_dict.keys())
    costs = {}
    for key in prod_dict:
        costs[key] = prod_dict[key][2]
    exps = {}
    for key in prod_dict:
        exps[key] = prod_dict[key][0]/prod_dict[key][1]
    upperBound = math.ceil(target_value/max([prod_dict[a][0]/prod_dict[a][1] for a in prod_dict]))\
    *max([prod_dict[a][0]/prod_dict[a][1] for a in prod_dict])
    prob = pulp.LpProblem('optimal_count', pulp.LpMinimize)
    prods_vars = pulp.LpVariable.dicts('prods', prods, lowBound=0, cat=pulp.LpInteger)

    prob += (pulp.lpSum([costs[i] * prods_vars[i] for i in prods]),"total_cost")
    prob += (pulp.lpSum([exps[i] * prods_vars[i] for i in prods]) >= target_value, "lowerBound")
    prob += (pulp.lpSum([exps[i] * prods_vars[i] for i in prods]) <= upperBound, "upperBound")

    prob.solve()
    optimal_set = {}
    for v in prob.variables():
        optimal_set[v.name.replace('prods_', '')] = {'CPU': prod_dict[v.name.replace('prods_', '')][2], 
                                                     'Amount': v.varValue, 
                                                     'Cost': prod_dict[v.name.replace('prods_', '')][2]*v.varValue}

    result_dict = {}
    result_dict['Target_value'] = target_value
    result_dict['Optimal_set'] = optimal_set
    result_dict['Cost_total'] = sum([optimal_set[a]['Cost'] for a in optimal_set])

    return result_dict

但是，我想使用 scipy.optimize.linprog 或 scipy.optimize.milp 重现此解决方案，但我在理解这些方法的设置时遇到了困难。

目前，我用 linprog 和 milp 得到的只是一个仅满足一个要求的解决方案 - 足以为给定区域着色

linprog代码：

from scipy.optimize import linprog
import math
pdict = {'Can_9ltr':[9, 0.17, 4870],
            'Can_4.5ltr':[4.5, 0.17, 2910],
            'Can_1ltr':[1, 0.17, 632],
            'Can_2.25ltr':[2.25, 0.17, 1790]}
square = 30
c = []
for key in pdict:
    c.append(pdict[key][2])
exps = []
for key in pdict:
    exps.append(pdict[key][0]/pdict[key][1])
A_ub = [[(1/c[0])*exps[0], (1/c[1])*exps[1], (1/c[2])*exps[2], (1/c[3])*exps[3]],
        [(1/c[0])*exps[0]*-1, (1/c[1])*exps[1]*-1, (1/c[2])*exps[2]*-1, (1/c[3])*exps[3]*-1]]
b_ub = [math.ceil(square/max(exps))*max(exps), square*-1]
integrality=[1, 1, 1, 1]
res = linprog(c, A_ub, b_ub, integrality=integrality)
print(list(res.x))

milp代码：

from scipy.optimize import milp, LinearConstraint
import math

pdict = {'Can_9ltr':[9, 0.17, 3980],
            'Can_4.5ltr':[4.5, 0.17, 2536],
            'Can_1ltr':[1, 0.17, 517],
            'Can_2.25ltr':[2.25, 0.17, 1470]}
square = 30
c = []
for key in pdict:
    c.append(pdict[key][2])
exps = []
for key in pdict:
    exps.append(pdict[key][0]/pdict[key][1])    
Ac = [[(1/c[0])*exps[0], (1/c[1])*exps[1], (1/c[2])*exps[2], (1/c[3])*exps[3]],
        [(1/c[0])*exps[0], (1/c[1])*exps[1], (1/c[2])*exps[2], (1/c[3])*exps[3]]]
b_u = [math.ceil(square/max(exps))*max(exps)]
b_l = [square]
integrality = [1, 1, 1, 1]
constraints = LinearConstraint(Ac, b_l, b_u)
res = milp(c=c, constraints=constraints, integrality=integrality)
print(list(res.x))

linprog 和 milp 的解决方案相同：

[0.0, 0.0, 3224.0, 0.0]

两个关键问题：

• 我不知道如何强制整数系数 - 3224.0 是 Can_1ltr 单位成本的 5.1。选项完整性 = [1, 1, 1, 1] - 我不确定我是否正确使用了它，或者它是否按我的预期工作。

• 我不明白为什么这两种方法都返回只考虑一个单位的解决方案，而不是最小化整个函数。

Answer 1

这是等价的。 Pandas 是可选的，但有助于理解解决方案。

import numpy as np
import pandas as pd
import math

from scipy.optimize import milp, Bounds, LinearConstraint

df = pd.DataFrame(
    data={
        'volume': (9, 4.5, 1, 2.25),  # litres
        'consume': (0.17, 0.17, 0.17, 0.17),  # ?? per m2
        'price': (4870, 2910, 632, 1790),  # ?? per can
    },
)
df['exp'] = df['volume']/df['consume']
n = len(df)
target_value = 30
max_prod = df['exp'].max()
max_exp = math.ceil(target_value / max_prod)*max_prod

result = milp(
    c=df['price'],
    integrality=np.ones(n, dtype=np.uint8),
    bounds=Bounds(lb=np.zeros(n)),
    constraints=LinearConstraint(A=df['exp'], lb=target_value, ub=max_exp),
)
assert result.success, result.message
df['prod'] = result.x
print(df)

   volume  consume  price        exp  prod
0    9.00     0.17   4870  52.941176   0.0
1    4.50     0.17   2910  26.470588   1.0
2    1.00     0.17    632   5.882353   1.0
3    2.25     0.17   1790  13.235294   0.0