我正试图在Google OR工具中解决多背包示例的一个变体。我似乎无法编码的一个特征是对值的软限制。
在原始示例中，项目具有用于计算约束的权重和用于计算最优解的值。在我的变体中，我有多种重量/容量，这些重量/容量构成了某些类型物品的配额和兼容性。此外，每个垃圾箱都有一个资金目标，每个物品都有价值。我想尽量减少每个垃圾箱的资金短缺：
# pseudocode!
minimise: sum(max(0, funding_capacity[j] - sum(item[i, j] * item_value[i] for i in num_items)) for j in num_bins)
该方法与示例之间的关键区别在于，如果item_1的值为110，而bin_a的资金需求为100，则item_1可以适应bin_a，并使资金缺口为零。值为50的item_2也可以适应bin_a(只要满足其他约束(，但是优化器将看不到目标函数的改进。我曾尝试使用objective.SetCoefficient方法来计算资金短缺，但我不断出现错误，我认为这与这种方法有关，不喜欢sum等聚合函数。
我如何在目标函数或约束条件下实现上述资金短缺目标？如何使用汇总计算形成目标函数理想的答案是Python中OR工具的代码片段，但其他编程语言中OR工具提供的清晰说明性答案也会有所帮助。
工作代码如下，但以下是如何进行公式化。
这里给出的多背包问题的公式变化
-
每个bin需要两组新变量。让我们称它们为
shortfall[j](连续(和filled[j](布尔(。 -
Shorfall[j]只是funding_requirement[j] - sum_i(funding[items i]) -
filled[j]是一个布尔值，如果bin中每个项目的资金之和大于其资金需求，则我们希望其为1，否则为0。 -
我们不得不求助于整数编程中的一个标准技巧，即使用大M(一个大数字(
if total_item_funding >= requirement, filled = 1 if total_item_funding < requirement, filled = 0
这可以用线性约束表示：
shortfall + BigM * filled > 0
请注意，如果不足为负，则会强制filled变量变为1。如果shortfall为阳性，则filled可以保持为0。(我们将使用目标函数强制执行。(
在最大化问题的目标函数中，对填充的变量进行惩罚。
Obj: Max sum(i,j) Xij * value_i + sum(j) filled_j * -100
因此，这种多背包配方被激励接近每个垃圾箱的资金要求，但如果它超过了要求，就会支付罚款。
你可以利用目标函数变量和惩罚。
使用Google OR工具制定
工作Python代码。为了简单起见，我只做了3个箱子。
from ortools.linear_solver import pywraplp
def create_data_model():
"""Create the data for the example."""
data = {}
weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
item_funding = [50, 17, 38, 45, 65, 60, 15, 30, 10, 25, 75, 30, 40, 40, 35]
data['weights'] = weights
data['values'] = values
data['i_fund'] = item_funding
data['items'] = list(range(len(weights)))
data['num_items'] = len(weights)
num_bins = 3
data['bins'] = list(range(num_bins))
data['bin_capacities'] = [100, 100, 80,]
data['bin_funding'] = [100, 100, 50,]
return data
def main():
data = create_data_model()
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')
# Variables
# x[i, j] = 1 if item i is packed in bin j.
x , short, filled = {}, {}, {}
for i in data['items']:
for j in data['bins']:
x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))
BIG_M, MAX_SHORT = 1e4, 500
for j in data['bins']:
short[j] = solver.NumVar(-MAX_SHORT, MAX_SHORT,
'bin_shortfall_%i' % (j))
filled[j] = solver.IntVar(0,1, 'filled[%i]' % (i))
# Constraints
# Each item can be in at most one bin.
for i in data['items']:
solver.Add(sum(x[i, j] for j in data['bins']) <= 1)
for j in data['bins']:
# The amount packed in each bin cannot exceed its capacity.
solver.Add(
sum(x[(i, j)] * data['weights'][i]
for i in data['items']) <= data['bin_capacities'][j])
#define bin shortfalls as equality constraints
solver.Add(
data['bin_funding'][j] - sum(x[(i, j)] * data['i_fund'][i]
for i in data['items']) == short[j])
# If shortfall is negative, filled is forced to be true
solver.Add(
short[j] + BIG_M * filled[j] >= 0)
# Objective
objective = solver.Objective()
for i in data['items']:
for j in data['bins']:
objective.SetCoefficient(x[(i, j)], data['values'][i])
for j in data['bins']:
# objective.SetCoefficient(short[j], 1)
objective.SetCoefficient(filled[j], -100)
objective.SetMaximization()
print('Number of variables =', solver.NumVariables())
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print('OPTMAL SOLUTION FOUNDnn')
total_weight = 0
for j in data['bins']:
bin_weight = 0
bin_value = 0
bin_fund = 0
print('Bin ', j, 'n')
print(f"Funding {data['bin_funding'][j]} Shortfall
{short[j].solution_value()}")
for i in data['items']:
if x[i, j].solution_value() > 0:
print('Item', i, '- weight:', data['weights'][i], ' value:',
data['values'][i], data['i_fund'][i])
bin_weight += data['weights'][i]
bin_value += data['values'][i]
bin_fund += data['i_fund'][i]
print('Packed bin weight:', bin_weight)
print('Packed bin value:', bin_value)
print('Packed bin Funding:', bin_fund)
print()
total_weight += bin_weight
print('Total packed weight:', total_weight)
else:
print('The problem does not have an optimal solution.')
if __name__ == '__main__':
main()
希望这能帮助你前进。