建模思路¶
带冲突的装箱问题(BPPC)的 OptAgent 模型使用 集合决策变量。对每个箱子,我们定义一个集合变量,表示分配到该箱子中的物品集合。我们对集合变量施加划分约束,以确保每个物品恰好被放入一个箱子中。
我们使用集合上的可变参数 sum 算子,以及一个返回任意物品索引对应重量的 lambda 函数,来计算每个箱子的总重量。请注意,该 sum 中的项数在搜索过程中会变化,因为集合的大小可以变化。
我们借助 find 算子来获取包含每个物品的箱子索引。通过使用 intersection 算子,我们可以施加冲突约束。具体而言,对于每个物品,我们计算其所在箱子中与之相冲突物品的索引集合,要求该集合为空。
当一个箱子至少包含一个物品时,它才被实际使用。借助 count 算子(返回集合中的元素数量),我们可以检查每个箱子是否被实际使用,从而计算所使用的箱子总数。
该模型对最优箱子数量计算了简单的下界与上界。它仅定义 nbMaxBins 个集合变量,并使用 solve(..., objective_threshold=...) 在找到使用不超过该下界的箱子的解时停止搜索。
Python 实现¶
import math
from pathlib import Path
from optagent import OptModel, solve
def read_instance(filename):
"""Read a BPPC instance file.
Each line after the header describes an item:
- id (1-based, ignored in favor of line order)
- weight
- forbidden item ids (1-based)
"""
weights_data: list[int] = []
forbidden_data: list[list[int]] = []
with open(filename, encoding="utf-8") as f:
first = True
for line in f:
tokens = line.split()
if first:
nb_items = int(tokens[0])
bin_capacity = int(tokens[1])
first = False
continue
weights_data.append(int(tokens[1]))
forbidden_data.append([int(x) - 1 for x in tokens[2:]])
return nb_items, bin_capacity, weights_data, forbidden_data
def main(
input_file, output_file=None, time_limit=5
):
nb_items, bin_capacity, weights_data, forbidden_data = read_instance(input_file)
nb_items = len(weights_data)
nb_min_bins = int(math.ceil(sum(weights_data) / float(bin_capacity)))
nb_max_bins = nb_items
model = OptModel()
# Set decisions: bins[k] represents the items in bin k
bins = [model.set(nb_items) for k in range(nb_max_bins)]
bins_array = model.array(bins)
# Find the bin where each item is packed
bin_for_item = [model.find(bins_array, i) for i in range(nb_items)]
# Each item must be in one bin and one bin only
model.constraint(model.partition(bins))
# Create an array and a function to retrieve the item's weight
weights = model.array(weights_data)
weight_lambda = model.lambda_function(lambda i: model.at(weights, i))
# Forbidden constraint for each item: conflicting items must live in different bins
for i in range(nb_items):
for j in forbidden_data[i]:
if j > i:
continue # enforce each pair only once
model.constraint(
bin_for_item[i] != bin_for_item[j]
)
# Weight constraint for each bin
bin_weights = [model.sum(b, weight_lambda) for b in bins]
for w in bin_weights:
model.constraint(w <= bin_capacity)
# Bin k is used if at least one item is in it
bins_used = [model.count(b) > 0 for b in bins]
# Count the used bins
total_bins_used = model.sum(*bins_used)
# Minimize the number of used bins
model.minimize(total_bins_used)
solution = solve(model, time_limit_s=float(time_limit))
result_values = {'total_bins_used': total_bins_used.value, **{f'bin_{k}': bin_var.value for k, bin_var in enumerate(bins)}}
lines = []
for k in range(nb_max_bins):
items = sorted(int(item) for item in result_values[f"bin_{k}"])
if not items:
continue
weight_value = int(sum(weights_data[i] for i in items))
line = f"Bin weight: {weight_value} | Items: " + " ".join(str(i) for i in items)
lines.append(line)
header = (
f"Nb items = {nb_items}; Bin capacity = {bin_capacity}; "
f"Min bins = {nb_min_bins}; Total bins used = {int(result_values['total_bins_used'])}; "
f"Status = {solution.feasible}"
)
print(header)
for line in lines:
print(line)
if output_file is not None:
with Path(output_file).open("w", encoding="utf-8") as f:
f.write(header + "\n")
for k in range(nb_items):
f.write(f"item:{k} Weight:{weights_data[k]}\n")
f.write("\n".join(lines) + "\n")
return solution
本地运行¶
Notebook 直接调用 main 并显式传入实例路径。以下代码格相互独立，可以按需要单独运行；调整 time_limit 可以控制每个实例的求解时间。
from pathlib import Path
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_bppc_1 = main(INSTANCE_DIR / "BPPC_1_0_2.txt", time_limit=1)
# 大量的物品冲突关系存在更多节点数量，难度提高了
solution_bppc_2 = main(INSTANCE_DIR / "BPPC_2_2_2.txt", time_limit=1)
solution_bppc_3 = main(INSTANCE_DIR / "BPPC_3_1_3.txt", time_limit=1)