我正在尝试找到一种方法，让尽可能少的盒子来装化学品袋。一个箱子的重量不能超过 3.3 公斤，但必须高于 2.7 公斤。我遇到了谷歌的 OR 工具，但我正在努力对约束进行编程。
当我将我的行李重量输入 OR 工具的装箱程序（如下）以及箱子重量的上限“bin_capacity_upper_limit”和“bin_capacity_lower_limit”时，我没有得到解决方案。
有什么办法可以得到近似解吗？也许通过隔离阻止获得最佳解决方案的袋子。我是 OR 工具或一般优化的新手。我将不胜感激任何帮助或建议。
from ortools.linear_solver import pywraplp
def create_data_model():
"""Create the data for the example."""
data = {}
weights = [1.0, 1.001, 1.09, 1.002, 1.006, 1.007, 1.0, .674, 1.002 , .22, .36, .24, 1.20, .4, .947, .987, .456]
data['weights'] = weights
data['items'] = list(range(len(weights)))
data['bins'] = data['items']
data['bin_capacity_upper_limit'] = 3.3
data['bin_capacity_lower_limit'] = 2.7
return data
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')
data = create_data_model()
# 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[j] = 1 if bin j is used.
y = {}
for j in data['bins']:
y[j] = solver.IntVar(0, 1, 'y[%i]' % j)
# Constraints
# Each item must be in exactly one bin.
for i in data['items']:
solver.Add(sum(x[i, j] for j in data['bins']) == 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']) <= y[j] *
data['bin_capacity_upper_limit'])
solver.Add(
sum(x[(i, j)] * data['weights'][i] for i in data['items']) >= y[j] *
data['bin_capacity_lower_limit'])
# Objective: minimize the number of bins used.
solver.Minimize(solver.Sum([y[j] for j in data['bins']]))
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
num_bins = 0
for j in data['bins']:
if y[j].solution_value() == 1:
bin_items = []
bin_weight = 0
for i in data['items']:
if x[i, j].solution_value() > 0:
bin_items.append(i)
bin_weight += data['weights'][i]
if bin_items:
num_bins += 1
print('Bin number', j)
print(' Items packed:', bin_items)
print(' Total weight:', bin_weight)
print()
print()
print('Number of bins used:', num_bins)
print('Time = ', solver.WallTime(), ' milliseconds')
else:
print('The problem does not have an optimal solution.')
首先，值得注意的是：您的实施速度非常慢，因为它没有利用您的垃圾箱容量限制对使用的垃圾箱数量设置下限和上限这一事实。引入这个将我的可行性检查从“几分钟所以我决定终止它”移动到 0.21 秒。
下一步：正如@sascha 所说，您需要选择您所说的近似解决方案以及您打算如何牺牲物品。我在这里提出一种方法，只需要牺牲一个选项并在 0.03 秒内完成。我没有 or-tools 所以我在 PuLP 中演示。
import pulp
import numpy as np
weights = np.array((
1. , 1.001, 1.09 , 1.002, 1.006, 1.007, 1. , 0.674, 1.002,
0.22 , 0.36 , 0.24 , 1.2 , 0.4 , 0.947, 0.987, 0.456))
items = np.arange(len(weights))
bin_capacity_upper_limit = 3.3
bin_capacity_lower_limit = 2.7
absolute_lower = round(np.ceil(weights.sum() / bin_capacity_upper_limit))
absolute_upper = round(np.ceil(weights.sum() / bin_capacity_lower_limit))
bins = np.arange(absolute_upper)
def prove_infeasible():
solver = pulp.LpProblem(name='chemical_knapsack_exact', sense=pulp.LpMinimize)
# x[i, j] = 1 if item i is packed in bin j.
assignments = pulp.LpVariable.dicts(
name='assign', cat=pulp.LpBinary,
indices=[(i, j) for i in items for j in bins])
# y[j] = 1 if bin j is used. All bins below the lower bound are used (those vars are fixed).
bins_used = [
pulp.LpVariable(
name=f'bin_{j}', cat=pulp.LpBinary,
lowBound=1 if j < absolute_lower else 0)
for j in bins]
for i in items:
# Each item must be in exactly one bin.
solver.addConstraint(
name=f'assign_excl_{i}',
constraint=pulp.lpSum([
assignments[i, j]
for j in bins
]) == 1)
for j in bins:
# The amount packed in each bin cannot exceed its capacity.
weight = pulp.lpDot(weights,
[assignments[i, j] for i in items])
used = bins_used[j]
solver.addConstraint(
name=f'weight_hi_{j}',
constraint=weight <= used*bin_capacity_upper_limit)
solver.addConstraint(
name=f'weight_lo_{j}',
constraint=weight >= used*bin_capacity_lower_limit)
# Objective: minimize the number of bins used.
solver.objective = pulp.lpSum(bins_used)
solver.solve()
assert solver.status == pulp.LpStatusInfeasible
def solve_approximate():
"""
Preserve as exact the originally intended number of bins, and the lower and upper capacity
limits. This implies that absolute_upper is still true.
Sacrifice some items to achieve feasibility. This means that absolute_lower is no longer true
because some of the weights may be unused.
"""
solver = pulp.LpProblem(name='chemical_knapsack_approx', sense=pulp.LpMaximize)
# x[i, j] = 1 if item i is packed in bin j.
assignments = pulp.LpVariable.dicts(
name='assign', cat=pulp.LpBinary,
indices=[(i, j) for i in items for j in bins])
# y[j] = 1 if bin j is used.
bins_used = pulp.LpVariable.dicts(
name=f'bin', cat=pulp.LpBinary, indices=bins)
for i in items:
# Each item must be in up to one bin.
solver.addConstraint(
name=f'assign_excl_{i}',
constraint=pulp.lpSum([
assignments[i, j]
for j in bins
]) <= 1)
for j in bins:
# The amount packed in each bin cannot exceed its capacity.
weight = pulp.lpDot(weights,
[assignments[i, j] for i in items])
used = bins_used[j]
solver.addConstraint(
name=f'weight_hi_{j}',
constraint=weight <= used*bin_capacity_upper_limit)
solver.addConstraint(
name=f'weight_lo_{j}',
constraint=weight >= used*bin_capacity_lower_limit)
# Objective: minimize the number of bins used and maximize the number of items packed.
# Tweak value and cost to taste.
item_value = 1
bin_cost = 1
solver.objective = item_value*pulp.lpSum(assignments.values()) - bin_cost*pulp.lpSum(bins_used)
print(solver)
solver.solve()
assert solver.status == pulp.LpStatusOptimal
for j in bins:
assigned = np.array([assignments[i,j].value() for i in items], dtype=int)
print(f'Bin {j} is', ' used,' if bins_used[j].value() else 'unused,',
f'{assigned.sum()} items, {assigned.dot(weights):.4f} weight')
for i in items:
bin_idx = next((j for j in bins if assignments[i,j].value()), None)
print(f'Item {i} is', 'unused' if bin_idx is None else f'in bin {bin_idx}')
prove_infeasible()
solve_approximate()
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
...
Result - Problem proven infeasible
No feasible solution found
Enumerated nodes: 0
Total iterations: 1931
Time (CPU seconds): 0.21
Time (Wallclock seconds): 0.21
chemical_knapsack_approx:
MAXIMIZE
1*assign_(0,_0) + ... + 1*assign_(9,_3) + 1*assign_(9,_4) + 1*assign_(9,_5) + -1*bin_0 + -1*bin_1 + -1*bin_2 + -1*bin_3 + -1*bin_4 + -1*bin_5 + 0
SUBJECT TO
assign_excl_0: assign_(0,_0) + assign_(0,_1) + assign_(0,_2) + assign_(0,_3)
+ assign_(0,_4) + assign_(0,_5) <= 1
...
weight_hi_0: assign_(0,_0) + 1.001 assign_(1,_0) + 0.36 assign_(10,_0)
+ 0.24 assign_(11,_0) + 1.2 assign_(12,_0) + 0.4 assign_(13,_0)
+ 0.947 assign_(14,_0) + 0.987 assign_(15,_0) + 0.456 assign_(16,_0)
+ 1.09 assign_(2,_0) + 1.002 assign_(3,_0) + 1.006 assign_(4,_0)
+ 1.007 assign_(5,_0) + assign_(6,_0) + 0.674 assign_(7,_0)
+ 1.002 assign_(8,_0) + 0.22 assign_(9,_0) - 3.3 bin_0 <= 0
weight_lo_0: assign_(0,_0) + 1.001 assign_(1,_0) + 0.36 assign_(10,_0)
+ 0.24 assign_(11,_0) + 1.2 assign_(12,_0) + 0.4 assign_(13,_0)
+ 0.947 assign_(14,_0) + 0.987 assign_(15,_0) + 0.456 assign_(16,_0)
+ 1.09 assign_(2,_0) + 1.002 assign_(3,_0) + 1.006 assign_(4,_0)
+ 1.007 assign_(5,_0) + assign_(6,_0) + 0.674 assign_(7,_0)
+ 1.002 assign_(8,_0) + 0.22 assign_(9,_0) - 2.7 bin_0 >= 0
...
Result - Optimal solution found
Objective value: 12.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.03
Time (Wallclock seconds): 0.03
Bin 0 is used, 3 items, 3.0780 weight
Bin 1 is used, 4 items, 3.1740 weight
Bin 2 is unused, 0 items, 0.0000 weight
Bin 3 is used, 4 items, 3.0760 weight
Bin 4 is unused, 0 items, 0.0000 weight
Bin 5 is used, 5 items, 3.2580 weight
Item 0 is in bin 3
Item 1 is in bin 0
Item 2 is in bin 0
Item 3 is in bin 5
Item 4 is unused
Item 5 is in bin 1
Item 6 is in bin 1
Item 7 is in bin 3
Item 8 is in bin 3
Item 9 is in bin 1
Item 10 is in bin 5
Item 11 is in bin 5
Item 12 is in bin 5
Item 13 is in bin 3
Item 14 is in bin 1
Item 15 is in bin 0
Item 16 is in bin 5