基于PuLP实现列生成法求解一维下料问题的技术求助

1. 定义核心参数 #

先把你的问题参数明确映射到代码变量：

• 原始板材长度：L = 100
• 成品规格与需求：
  • 规格列表：sizes = [45, 36, 31, 14]
  • 需求数量：demands = [9700, 61000, 39500, 21100]
• 单根原始板材成本：cost_per_board = 100（对应初始目标505×100=50500美元）

2. 配置初始下料模式 #

替换成你实际的4种初始模式（示例为常见合理模式，可直接修改）：

import pulp

# 初始下料模式：每行代表一种模式，元素对应各规格的下料数量（总长度≤100）
initial_patterns = [
    [2, 0, 0, 0],   # 2根45（总长度90）
    [0, 2, 0, 2],   # 2根36 + 2根14（总长度100）
    [0, 0, 3, 0],   # 3根31（总长度93）
    [0, 0, 0, 7]    # 7根14（总长度98）
]
n_patterns = len(initial_patterns)

3. 构建主问题（Master Problem） #

主问题是线性规划，变量为各下料模式的使用量，约束满足需求，目标最小化总成本：

# 初始化主问题
master_problem = pulp.LpProblem("Cutting_Stock_Master", pulp.LpMinimize)

# 定义变量：每种模式的板材使用量（先放松为连续变量，迭代后转整数）
pattern_vars = pulp.LpVariable.dicts(
    "Pattern", 
    range(n_patterns), 
    lowBound=0, 
    cat='Continuous'
)

# 目标函数：总成本 = 模式使用量 × 单板材成本
master_problem += pulp.lpSum([pattern_vars[i] * cost_per_board for i in range(n_patterns)]), "Total_Cost"

# 需求约束：每种规格的下料总数≥需求
for j in range(len(sizes)):
    master_problem += pulp.lpSum([initial_patterns[i][j] * pattern_vars[i] for i in range(n_patterns)]) >= demands[j], f"Demand_Constraint_{sizes[j]}"

4. 构建子问题（Pricing Problem） #

子问题是背包问题，用于寻找能降低总成本的新下料模式：

def solve_pricing_problem(dual_prices):
    # 初始化子问题（最大化减少成本）
    pricing_problem = pulp.LpProblem("Cutting_Stock_Pricing", pulp.LpMaximize)
    
    # 变量：新模式中各规格的下料数量（非负整数）
    x = pulp.LpVariable.dicts(
        "x", 
        range(len(sizes)), 
        lowBound=0, 
        cat='Integer'
    )
    
    # 目标函数：减少成本 = Σ(对偶价格[j]×下料数量[j]) - 1
    pricing_problem += pulp.lpSum([dual_prices[j] * x[j] for j in range(len(sizes))]) - 1, "Reduced_Cost"
    
    # 长度约束：下料总长度≤原始板材长度
    pricing_problem += pulp.lpSum([sizes[j] * x[j] for j in range(len(sizes))]) <= L, "Length_Constraint"
    
    # 求解子问题（关闭日志输出）
    pricing_problem.solve(pulp.PULP_CBC_CMD(msg=0))
    
    # 获取结果
    reduced_cost = pulp.value(pricing_problem.objective)
    new_pattern = [int(pulp.value(x[j])) for j in range(len(sizes))]
    
    return reduced_cost, new_pattern

5. 列生成循环迭代 #

循环求解主问题→获取对偶价格→求解子问题→添加新模式，直到无更优模式：

# 迭代循环
iteration = 0
while True:
    iteration += 1
    print(f"Iteration {iteration}")
    
    # 求解主问题
    master_problem.solve(pulp.PULP_CBC_CMD(msg=0))
    current_cost = pulp.value(master_problem.objective)
    print(f"当前总成本: {current_cost}")
    
    # 获取约束对偶价格
    dual_prices = [master_problem.constraints[f"Demand_Constraint_{sizes[j]}"].pi for j in range(len(sizes))]
    print(f"对偶价格: {dual_prices}")
    
    # 求解子问题
    reduced_cost, new_pattern = solve_pricing_problem(dual_prices)
    print(f"新模式减少成本: {reduced_cost}")
    print(f"新模式: {new_pattern}")
    
    # 终止条件：减少成本≤0（无更优模式）
    if reduced_cost <= 1e-6:
        break
    
    # 将新模式加入主问题
    pattern_vars[n_patterns] = pulp.LpVariable(f"Pattern_{n_patterns}", lowBound=0, cat='Continuous')
    master_problem += pattern_vars[n_patterns] * cost_per_board
    # 更新各需求约束
    for j in range(len(sizes)):
        master_problem.constraints[f"Demand_Constraint_{sizes[j]}"].addterm(pattern_vars[n_patterns], new_pattern[j])
    
    n_patterns += 1

# 迭代结束后，求解整数解
for var in pattern_vars.values():
    var.cat = 'Integer'

master_problem.solve(pulp.PULP_CBC_CMD(msg=0))
final_cost = pulp.value(master_problem.objective)
print(f"\n最终整数解总成本: {final_cost}")
print("模式使用情况:")
for i in range(n_patterns):
    if pulp.value(pattern_vars[i]) > 1e-6:
        pattern = initial_patterns[i] if i < len(initial_patterns) else new_pattern
        print(f"模式{i+1} ({pattern}): {int(pulp.value(pattern_vars[i]))} 根板材")

关键适配点 #

• 初始模式替换：直接修改initial_patterns为你实际的4种下料模式，确保总长度≤100。
• 对偶价格验证：迭代中输出的对偶价格会逐步收敛，可对比你提供的初始值(0.5,0.5,0.25,0.25)观察趋势。
• 成本调整：若你的成本计算逻辑不同，直接修改cost_per_board参数即可。

内容的提问来源于stack exchange，提问作者ky18