python调用SCIP求解下料问题（Cutting Stock Problem）

1. 问题示例

下料问题（Cutting Stock Problem，CSP）也叫板材切割问题。例如，有一批长度为110cm的板材（且称之为母料），需要切割成不同尺寸的小板材，例如下图所示，20cm的需要48个，45cm的需要35个, …，请问怎样切割，才能最省母料。

2. 数学模型

• 数学模型直接参考《Column Generation》第五章中的Kantorovich Model
  
  

3. python调用开源求解器SCIP代码

• python代码

import os
import pandas as pd
import numpy as np
import pyscipopt as opt# ========== 测试算例 ==========
W = 100  # 原料板材的长度
w = [3, 6 ,7, 11]  # 制造产品i需要的长度
b = [250, 200, 180, 100]  # 产品i的总需求量
I = len(w)  # 产品种类的数量
K = 100  # 假设原料板材的个数 (其实这个值可以提前预处理计算)model = opt.Model('MCP')
# ========== 定义变量 ==========
x0 = {}  
x = {}
# x0_k: 0-1变量，原料板材k是否被使用
for k in range(K):x0[k] = model.addVar(vtype='B', name='roll_' + str(k))# x_i_k: 在原料板材k中，切割产品i的数量
for i in range(I):for k in range(K):x[i, k] = model.addVar(vtype='C', name='num_' + str(i) + '_' + str(k))# ========== 定义约束 ==========
# 约束1: 所有切割得到产品i，满足需求
for i in range(I):model.addCons(opt.quicksum(x[i, k] for k in range(K)) >= b[i], name='demand_' + str(i))# 约束2: 如果原材料k被使用，则其切割的产品的总长度不能超过板材长度W
for k in range(K):model.addCons(opt.quicksum(x[i, k] * w[i] for i in range(I)) <= x0[k] * W, name='width_' + str(k))# 约束3: 原材料K是一样的，没有类似序列的属性, 可能多个解对应一样的切割方案，让选中的原料板材都在前面序列
for k in range(K-1):model.addCons(x0[k] >= x0[k+1])# ==========定义目标==========
# 目标: 原料板材使用数量最小
model.setObjective(opt.quicksum(x0[k] for k in range(K)))
model.setMinimize()
model.optimize()# ========== 输出结果 ==========
print('model_status = ', model.getGap())
print('model_gap =', model.getStatus())
print('model_obj =', model.getObjVal())roll_lst = []
for k in range(K):if model.getVal(x0[k]) > 0:roll_lst.append(k)
print(roll_lst)

• 结果
  

4. Todo

• 当算例达到一定规模时，使用求解器求解效率可能会变慢很多，可以使用列生成算法 (Column Generation) 进行求解

参考文献

《Column Generation》Guy Desaulniers (Editor), Jacques Desrosiers (Editor), Marius M. Solomon (Editor)， chapter 5