建模思路¶
装箱问题(BPP)的 OptAgent 模型使用 集合决策变量。对每个箱子,我们定义一个集合变量,表示分配到该箱子中的物品集合。我们对集合变量施加划分约束,以确保每个物品恰好被放入一个箱子中。
我们使用集合上的可变参数 sum 算子,以及一个返回任意物品索引对应重量的 lambda 函数,来计算每个箱子的总重量。请注意,该 sum 中的项数在搜索过程中会变化,因为集合的大小可以变化。
当一个箱子至少包含一个物品时,它才被实际使用。借助 count 算子(返回集合中的元素数量),我们可以检查每个箱子是否被实际使用,从而计算所使用的箱子总数。
该模型对最优箱子数量计算了简单的下界与上界。它仅定义 nbMaxBins 个集合变量,并使用 solve(..., objective_threshold=...) 在找到使用不超过该下界的箱子的解时停止搜索。
Python 实现¶
import math
from pathlib import Path
from optagent import OptModel, solve
def read_integers(filename):
with open(filename) as f:
return [int(elem) for elem in f.read().split()]
def main(input_file, output_file=None, time_limit=50):
file_it = iter(read_integers(input_file))
nb_items = int(next(file_it))
bin_capacity = int(next(file_it))
weights_data = [int(next(file_it)) for _ in range(nb_items)]
nb_min_bins = int(math.ceil(sum(weights_data) / float(bin_capacity)))
nb_max_bins = min(nb_items, 2 * nb_min_bins)
#
# Declare the optimization model
#
model = OptModel()
# Set decisions: bins[k] represents the items in bin k
bins = [model.set(nb_items) for k in range(nb_max_bins)]
# 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))
# 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)
# Stop once the first objective reaches the trivial lower bound
solution = solve(
model,
time_limit_s=float(time_limit),
objective_threshold={0: nb_min_bins},
)
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")
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_t120_00 = main(INSTANCE_DIR / "t120_00.txt", time_limit=1)
solution_t120_05 = main(INSTANCE_DIR / "t120_05.txt", time_limit=1)
solution_u120_00 = main(INSTANCE_DIR / "u120_00.txt", time_limit=1)