OR-Tools：0-1背包，对物品来源有限制
OR-Tools: 0-1 klapsack with constraint on item source
我正在尝试对物品来源进行 0-1 背包优化。我从 ortools 网站 (ortool example) 中获取了示例，并尝试添加一个约束，以便只能从背包中的每个所有者那里挑选一件物品。
我有一个包含相关权重 (data['weights'])、值 (data['values']) 和来源 (data['owns']) 的项目列表。我想找到放入背包的最佳物品组合，因为每个来源只能放入一件物品。
我不知道怎么写约束。
如果您查看下面的代码并有 1 个背包，那么最佳解决方案应该是最多从所有者 0 拿走 1 件物品，从所有者 1 拿走一件，从所有者 2 拿走一件，这遵循重量约束和唯一性挑选的物品数量（重量低于 100）。
这是我使用的代码（取自 ortool 多背包示例）：
from ortools.linear_solver import pywraplp
def create_data_model():
"""Create the data for the example."""
data = {}
data['weights'] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
data['values'] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
data['owns'] = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0]
data['owners'] = list(range(3))
data['items'] = list(range(len(data['weights'])))
data['num_items'] = len(data['weights'])
data['bins'] = []
data['bin_capacity'] = 100
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 = {}
for i in data['items']:
for j in data['bins']:
x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))
# y[i, j] = 1 if item i from owner j in bin.
y = {}
for i in data['owns']:
for j in data['owners']:
y[(i, j)] = solver.IntVar(0, 1, 'y_%i_%i' % (i, j))
# 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)
# Each item can be at from one owner.
# for i in data['items']:
# solver.Add(sum(y[i, j] for j in data['owners']) <= 1)
# The amount packed in each bin cannot exceed its capacity.
for j in data['bins']:
solver.Add(
sum(x[(i, j)] * data['weights'][i]
for i in data['items']) <= data['bin_capacity'])
# Objective
objective = solver.Objective()
for i in data['items']:
for j in data['bins']:
objective.SetCoefficient(x[(i, j)], data['values'][i])
objective.SetMaximization()
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print('Total packed value:', objective.Value())
total_weight = 0
for j in data['bins']:
bin_weight = 0
bin_value = 0
print('Bin ', j, '\n')
for i in data['items']:
if x[i, j].solution_value() > 0:
print('Item', i, '- weight:', data['weights'][i], ' value:',
data['values'][i])
bin_weight += data['weights'][i]
bin_value += data['values'][i]
print('Packed bin weight:', bin_weight)
print('Packed bin value:', bin_value)
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()
首先感谢提供答案的@sascha！
我附在代码下方（我使用 2 个垃圾箱，3 个不同的所有者）：
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
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]
owns = [0, 1, 2, 0, 1, 2, 2, 1, 0, 1, 2, 0, 0, 1, 2]
# owns = [0 for _ in range(len(weights))]
data['weights'] = weights
data['values'] = values
data['owners'] = [0, 1, 2]
data['owns'] = owns
data['items'] = list(range(len(weights)))
data['num_items'] = len(weights)
data['bins'] = list(range(2))
data['bin_capacities'] = [150, 100]
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 = {}
for i in data['items']:
for j in data['bins']:
x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))
# 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)
# Each item can be at from one owner.
for o in data['owners']:
for j in data['bins']:
owner = []
for i in data['items']:
if data['owns'][i] == o:
owner.append(x[i, j])
solver.Add(sum(owner) <= 1)
# The amount packed in each bin cannot exceed its capacity.
for j in data['bins']:
solver.Add(
sum(x[(i, j)] * data['weights'][i]
for i in data['items']) <= data['bin_capacities'][j])
# Objective
objective = solver.Objective()
for i in data['items']:
for j in data['bins']:
objective.SetCoefficient(x[(i, j)], data['values'][i])
objective.SetMaximization()
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print('Total packed value:', objective.Value())
total_weight = 0
for j in data['bins']:
bin_weight = 0
bin_value = 0
print('Bin ', j, '\n')
for i in data['items']:
if x[i, j].solution_value() > 0:
print('Item', i, '- weight:', data['weights'][i],
' value:', data['values'][i],
' owner:', data['owns'][i])
bin_weight += data['weights'][i]
bin_value += data['values'][i]
print('Packed bin weight:', bin_weight)
print('Packed bin value:', bin_value)
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()
我正在尝试对物品来源进行 0-1 背包优化。我从 ortools 网站 (ortool example) 中获取了示例，并尝试添加一个约束，以便只能从背包中的每个所有者那里挑选一件物品。
我有一个包含相关权重 (data['weights'])、值 (data['values']) 和来源 (data['owns']) 的项目列表。我想找到放入背包的最佳物品组合，因为每个来源只能放入一件物品。
我不知道怎么写约束。
如果您查看下面的代码并有 1 个背包，那么最佳解决方案应该是最多从所有者 0 拿走 1 件物品，从所有者 1 拿走一件，从所有者 2 拿走一件，这遵循重量约束和唯一性挑选的物品数量（重量低于 100）。
这是我使用的代码（取自 ortool 多背包示例）：
from ortools.linear_solver import pywraplp
def create_data_model():
"""Create the data for the example."""
data = {}
data['weights'] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
data['values'] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
data['owns'] = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0]
data['owners'] = list(range(3))
data['items'] = list(range(len(data['weights'])))
data['num_items'] = len(data['weights'])
data['bins'] = []
data['bin_capacity'] = 100
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 = {}
for i in data['items']:
for j in data['bins']:
x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))
# y[i, j] = 1 if item i from owner j in bin.
y = {}
for i in data['owns']:
for j in data['owners']:
y[(i, j)] = solver.IntVar(0, 1, 'y_%i_%i' % (i, j))
# 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)
# Each item can be at from one owner.
# for i in data['items']:
# solver.Add(sum(y[i, j] for j in data['owners']) <= 1)
# The amount packed in each bin cannot exceed its capacity.
for j in data['bins']:
solver.Add(
sum(x[(i, j)] * data['weights'][i]
for i in data['items']) <= data['bin_capacity'])
# Objective
objective = solver.Objective()
for i in data['items']:
for j in data['bins']:
objective.SetCoefficient(x[(i, j)], data['values'][i])
objective.SetMaximization()
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print('Total packed value:', objective.Value())
total_weight = 0
for j in data['bins']:
bin_weight = 0
bin_value = 0
print('Bin ', j, '\n')
for i in data['items']:
if x[i, j].solution_value() > 0:
print('Item', i, '- weight:', data['weights'][i], ' value:',
data['values'][i])
bin_weight += data['weights'][i]
bin_value += data['values'][i]
print('Packed bin weight:', bin_weight)
print('Packed bin value:', bin_value)
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()
首先感谢提供答案的@sascha！
我附在代码下方（我使用 2 个垃圾箱，3 个不同的所有者）：
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
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]
owns = [0, 1, 2, 0, 1, 2, 2, 1, 0, 1, 2, 0, 0, 1, 2]
# owns = [0 for _ in range(len(weights))]
data['weights'] = weights
data['values'] = values
data['owners'] = [0, 1, 2]
data['owns'] = owns
data['items'] = list(range(len(weights)))
data['num_items'] = len(weights)
data['bins'] = list(range(2))
data['bin_capacities'] = [150, 100]
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 = {}
for i in data['items']:
for j in data['bins']:
x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))
# 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)
# Each item can be at from one owner.
for o in data['owners']:
for j in data['bins']:
owner = []
for i in data['items']:
if data['owns'][i] == o:
owner.append(x[i, j])
solver.Add(sum(owner) <= 1)
# The amount packed in each bin cannot exceed its capacity.
for j in data['bins']:
solver.Add(
sum(x[(i, j)] * data['weights'][i]
for i in data['items']) <= data['bin_capacities'][j])
# Objective
objective = solver.Objective()
for i in data['items']:
for j in data['bins']:
objective.SetCoefficient(x[(i, j)], data['values'][i])
objective.SetMaximization()
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print('Total packed value:', objective.Value())
total_weight = 0
for j in data['bins']:
bin_weight = 0
bin_value = 0
print('Bin ', j, '\n')
for i in data['items']:
if x[i, j].solution_value() > 0:
print('Item', i, '- weight:', data['weights'][i],
' value:', data['values'][i],
' owner:', data['owns'][i])
bin_weight += data['weights'][i]
bin_value += data['values'][i]
print('Packed bin weight:', bin_weight)
print('Packed bin value:', bin_value)
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()