优化 | 从下料问题看整数计划中的列生成办法（附求解器源代码）

『运筹OR帷幄』原创

编者案：文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

列生成算法作为一种处理大范围线性计划问题的经常使用算法，在为NP-hard 问题设计启迪式算法方面亦有广泛的利用，同经常与DW分解联合使用。文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

该文首次编辑于2018.1.11，本次为旧文新发。文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

系列文章为『运筹OR帷幄』最新推出的版块之一，主要聚焦于经典算法的代码实现及案例可视化，或最新paper算法复现。目的是为了理论联络实际，以代码为基础让算法理论能够落地。文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

：文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

“列生成办法（Column Generation，CG）用来解决大型线性计划问题”，这是许多书中对列生成算法的描写至多的一句话，接下来的D-W分解（Dantzig-Wolfe decomposition），可能就让初学者迷迷糊糊，从理论到理论的证明其实不是工科生的强项，所以我换了一个角度来简单描写一以下生成办法的一个初步使用。旅行商问题（Travelling salesman problem,TSP），车辆路径问题（Vehicle Routing Problem,VRP），车间调度问题（scheduling）等一系列组合优化问题的下界（lower bound）求解方向的论文可以查得到许多，其中也有人使用拉格朗日松弛（lagrangian relaxation）等不同的求解技术。文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

优化对象：一维下料问题文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

1文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

一维下料问题的 一般描写是：钢材厂（或许是木材厂，铝材厂，造纸厂，e妹妹m..）有一批钢管数量为文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

，长度都为 文章源自微观生活（93wg.com）微观生活-https://93wg.com/6316.html

；假定有

个顾客，来钢厂下定单:每一位顾客需要长度为

（

，也就是下文切割规格 ）的钢管

根，优化的目标是:怎么切割钢管使得我既能知足客户的需求又使得的损耗的起码呢？

显然，在不加附加束缚的情况下，这是一个典型的0-1整数计划，可以参见 @留德华叫兽相关介绍，例如：

离散/整数/组合/非凸优化概述及其在AI的利用：http://t.cn/RohgcpT

而且咱们知道最差的情况是用料

，也就是我每一一根都拿来切，每一一根只切成

的长度。这样是很可耻的，剩下的拿来做金箍棒吗？？所以咱们得应用数学的气力！建模啊

• 模型1：一种直观的建模方式

第一步：肯定咱们的决策变量为

表示是不是写切割钢管i, 既然是整数计划，

的取值只能是整数。

在每一一根上咱们不可能只切割一种

；为确保最小挥霍，所以要尽量支配多的切割规格在一根钢管上，所以还需要添加变量

,表示在钢管i上切

次来知足客户j的需求。到此大家可能自己也把束缚想出来了：

优化目标：起码的切割钢管数

束缚1：无论怎么样咋切，顾客的请求一定知足（他们是上帝）

束缚2：我在选中的每一根钢管上切割，无论支配几个切割规格，加以及总不能大于我的钢管长度

（巧妇难为无米之炊）

这类方式e妹妹妹妹m...........不太数学，换一下

还是抽象？那具体到一个例子来看：

假定我的钢管长度为120米，总共有240根，现在有10个顾客，顾客的请求用Python随机生成如下：

demands = [10, 11, 11, 12, 12, 12, 10, 11, 12, 10]

lengths = [92, 59, 97, 32, 38, 55, 80, 75, 108, 57]

把上边束缚写开：

这样就比较清楚了，接下来，咱们用Python2.7写调用gurobi 求解器进行求解，咱们把程序录入

最大长
M =240 添加决策变量
for i in range:
for j in range:34;>=&34;demands&34;<=&34;withlimit&

waiting。。。。

。。。。。。

gurobi的求解进程

输出的最后的结果

以上截图是gurobi的log部份截图，咱们找到最优了！只需要切割72根，没错，时间就是这么长1295s，咱们的范围也不大，10客户都知足不了？？工厂恐怕每一天不止10个客户............不要想：一定是Python的问题！你可以用C++,C, 那就是求解器gurobi的问题，你可以选用cplex,。此模型在1939 年，由前苏联经济学家 Kantorovich 给出[1]

• 对模型1的反思