问题描述¶
在钢厂板坯设计问题中，我们需要将钢铁订单的生产组织到板坯中。钢厂通过将铁水浇铸成板坯来生产钢材。钢厂可生产有限数量的板坯规格。每个订单具有两个属性：颜色（对应于钢厂中的某条工艺路径）和重量。板坯具有最大容量：分配给某块板坯的订单总重量不得超过该容量。此外，由于将板坯切割后再送往钢厂的不同工序代价高昂，因此每块板坯中所包含的不同颜色数量是有限制的（通常为两种）。目标是最小化钢材浪费，即生产出来但未被任何订单使用的钢材数量。更多详情请参见 CSPLib。
学习要点¶
- 使用 OptAgent 的
set决策变量表示分配给各板坯的订单集合 - 使用
partition约束确保每个订单恰好分配给一块板坯 - 使用集合 lambda 动态计算板坯重量和不同颜色数量
数据¶
数据文件的格式如下：
- 第一行：板坯规格数以及所有可用的规格大小
- 第二行：颜色种类数
- 第三行：订单数量
- 接下来每一行描述一个订单：订单的规格大小和颜色
我们假设每块板坯最多只能包含两种不同颜色的订单。
建模思路¶
每块板坯使用一个 set 决策变量表示其订单集合，并通过 partition 约束使每个订单恰好属于一块板坯。
模型使用集合 lambda 汇总每块板坯的订单重量，并约束其不超过最大板坯规格；同时通过 distinct 统计订单颜色，限制每块板坯最多包含两种颜色。板坯浪费量由预计算表给出，即能够容纳当前订单总重量的最小板坯规格减去订单总重量。目标是最小化所有板坯的总浪费量。
Python 实现¶
from pathlib import Path
from optagent import OptModel, solve
def read_integers(filename):
return [
int(value)
for value in Path(filename).read_text(encoding="utf-8").split()
]
def read_instance(filename):
values = iter(read_integers(filename))
nb_slab_sizes = next(values)
slab_sizes = [next(values) for _ in range(nb_slab_sizes)]
nb_colors = next(values)
nb_orders = next(values)
quantities = []
colors = []
for _ in range(nb_orders):
quantities.append(next(values))
colors.append(next(values))
return slab_sizes, nb_colors, quantities, colors
def pre_compute_waste_for_content(slab_sizes, sum_size_orders):
if slab_sizes != sorted(slab_sizes):
raise ValueError("Slab sizes must be sorted in ascending order")
max_size = slab_sizes[-1]
waste_for_content = [0] * (max(sum_size_orders, max_size) + 1)
previous_size = 0
for size in slab_sizes:
for content in range(previous_size + 1, size):
waste_for_content[content] = size - content
previous_size = size
return waste_for_content
def main(input_file, output_file=None, time_limit=20):
slab_sizes, _nb_colors, quantities_data, colors_data = read_instance(
input_file
)
nb_colors_max_slab = 2
nb_orders = len(quantities_data)
nb_slabs = nb_orders
max_size = slab_sizes[-1]
waste_for_content = pre_compute_waste_for_content(
slab_sizes, sum(quantities_data)
)
model = OptModel()
colors = model.array(colors_data)
quantities = model.array(quantities_data)
color_lambda = model.lambda_function(lambda order: colors[order])
quantity_lambda = model.lambda_function(lambda order: quantities[order])
# Set decisions: slabs[s] contains the orders assigned to slab s.
slabs = [
model.set(nb_orders)
for s in range(nb_slabs)
]
model.constraint(model.partition(slabs))
slab_contents = []
for s, slab in enumerate(slabs):
distinct_colors = model.distinct(slab, color_lambda)
model.constraint(
model.count(distinct_colors) <= nb_colors_max_slab,
)
slab_content = model.sum(slab, quantity_lambda)
slab_contents.append(slab_content)
model.constraint(
slab_content <= max_size
)
waste_array = model.array(waste_for_content)
wasted_steel = [waste_array[content] for content in slab_contents]
total_wasted_steel = model.sum(*wasted_steel)
model.minimize(total_wasted_steel)
solution = solve(model, time_limit_s=float(time_limit))
if not solution.feasible:
print(f"No feasible slab design found; Status = {solution.status}")
return solution
used_slabs = [sorted(int(order) for order in slab.value) for slab in slabs]
used_slabs = [orders for orders in used_slabs if orders]
output_lines = [str(int(total_wasted_steel.value)), str(len(used_slabs))]
for orders in used_slabs:
output_lines.append(
f"{len(orders)} " + " ".join(str(order + 1) for order in orders)
)
result_text = "\n".join(output_lines)
print(f"Status = {solution.status}\n{result_text}")
if output_file is not None:
Path(output_file).write_text(result_text + "\n", encoding="utf-8")
return solution
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_12_orders = main(
INSTANCE_DIR / "12orderproblem.in",
time_limit=1,
)
solution_13_orders = main(
INSTANCE_DIR / "13orderproblem.in",
time_limit=1,
)
solution_14_orders = main(
INSTANCE_DIR / "14orderproblem.in",
time_limit=1,
)