特定约束Cutting-Stock/Bin-Packing算法及Python Pulp问题求助

需求与约束 #

• 输入：多种长度及对应数量的原料集合W，多种成品长度及对应需求量集合w
• 核心约束：不同原料不可混合使用——即同一种成品只能由某一种长度的原料切割生产，不能同时用多种不同长度的原料制作同一种成品
• 目标：最小化切割产生的废料总量

遇到的问题 #

已通过检索未找到匹配该约束的解决方案，尝试用Python pulp模块编写的代码无法满足“不同原料不可混合使用”的约束，现寻求以下帮助：

• 符合约束的线性规划算法思路
• 替代实现方案
• 伪代码或相关实现提示（不限编程语言）

本人编写的代码 #

import pulp

W = [6000, 6500, 7000, 7500, 8000, 8500, 9000, 10000, 11000, 12000]
Q = [20, 14, 50, 6, 300, 122, 15, 213, 22, 235]

w = [6000, 5300, 4700]
d = [4, 2, 2]

problem = pulp.LpProblem("CuttingStock", pulp.LpMinimize)

# y[i, j] 表示用第i种原料生产第j种成品的数量
x = [0] * len(W)
y = [[0] * len(w) for i in range(len(W))]
for i in range(len(W)):
    x[i] = pulp.LpVariable(f"x[{i}]", lowBound=0, cat=pulp.LpInteger)
    for j in range(len(w)):
        y[i][j] = pulp.LpVariable(
            f"y[{i}][{j}]", lowBound=0, cat=pulp.LpInteger)

# 目标函数：最小化废料总量
problem += pulp.lpSum(x[i] * W[i] - pulp.lpSum(w[j] * y[i][j] for j in range(len(w)))
                      for i in range(len(W)))

# 约束1：满足所有成品的需求量
for j in range(len(w)):
    problem += pulp.lpSum(y[i][j] for i in range(len(W))) == d[j]

# 约束2：每种原料的使用量不超过其可用数量
for i in range(len(W)):
    problem += x[i] <= Q[i]

# 约束3：单种原料切割的成品总长度不超过原料总长度
for i in range(len(W)):
    problem += (x[i] * W[i]) - pulp.lpSum(y[i][j] * w[j]
                                          for j in range(len(w))) >= 0

# 求解问题
problem.solve()

problem.writeLP("out.txt")

# 输出最优解
if pulp.LpStatus[problem.status] == 'Optimal':
    for i in range(len(W)):
        if x[i].value() != 0:
            print(f"W{i}, used {x[i].value()}")
        for j in range(len(w)):
            if y[i][j].value() > 0:
                print(
                    f"w {j}, produced {y[i][j].value()}")
    used = 0
    for i in range(len(W)):
        used += x[i].value() * W[i]
    print(used)
    if problem.objective.value() != 0:
        print(
            f"Final loss: {problem.objective.value()}\nLoss%: {(used / problem.objective.value()) * 100}%")
    else:
        print("No loss")
else:
    print("No optimal solution found.")

内容的提问来源于stack exchange，提问作者단과즙