运筹说 第21期 | 算法介绍之列生成算法

本期小编为大家介绍单纯形法的另一种拓展算法—列生成算法，主要从其产生背景、基本思想、应用实例、平台实现以及与单纯形法的区别和联系五个方面展开讲解，一起来看一看吧！

列生成算法（Column Generation Algorithm）是一种用于求解大规模线性优化问题的高效算法，其理论基础由Danzig等人于1960年提出。本质上来讲，列生成算法是单纯形法的一种形式，用来求解线性规划问题。

一、产生背景

在某些线性规划问题的模型中，约束条件的数目有限，但变量的数目会随着问题规模的增长爆炸式的增长，很难把所有的变量都显性的在模型中表达出来，这类问题就是大规模的线性规划问题。面对这类问题，单纯形法虽然能保证在数次迭代后找到最优解，但由于其需要对众多变量进行基变换，求解过程会异常繁琐。此外，在用单纯形法求解这类问题时，基变量只与约束条件的个数相关，每次迭代只会有一个新的非基变量进基，换言之，在整个求解过程中其实只有很少一部分变量会被涉及到。在这种背景下，研究人员基于单纯形法提出了列生成算法。

该算法不是直接同时处理所有的候选方案，而是基于当前生成的列的子集，通过限制主问题进行优化求解；其余的候选方案可以改善限制主问题当前最优解时，才会进入该子集。与单纯形法相比，列生成的进基变量是通过求解子问题生成的，而单纯形法的进基变量是模型存在的变量。

目前，列生成算法已被应用于求解很多著名的NP-hard优化问题，如机组人员调度问题（Crew assignment problem）、切割问题（Cutting stock problem）、车辆路径问题（Vehicle routing problem）、单资源工厂选址问题（The single facility location problem）等。

二、基本思想

列生成算法通过求解子问题（sub problem）来找到可以进基的非基变量，该非基变量在模型中并没有显性的写出来（可以看成是生成了一个变量，每个变量其实等价于一列，所以该方法被称为列生成算法）。如果找不到一个可以进基的非基变量，那么就意味着所有的非基变量的检验数（Reduced Cost，RC）都满足最优解的条件，也就是说，该线性规划的最优解已被找到。其思路如下：

1、先把原问题（Master Problem，MP）转换到一个规模更小（即变量数比原问题少）的问题上，这个只使用部分变量的模型被称为原问题的RMP 问题（Restricted Master Problem）。在RMP上用单纯形法求最优解，注意此时求得的最优解只是RMP上的，并不是MP的最优解。

2、然后需要通过一个子问题去检测在那些未被考虑的变量中是否有使得RC小于零的情况，如果有，那么就把这个变量的相关系数列加入到RMP的系数矩阵中，返回第1步。

经过反复迭代，直到子问题中的RC都大于等于零，此时就找到了MP的最优解。流程图如下：

三、应用实例

1、问题描述

有三种长度分别为9、14、16的木材，对应的成本价为5、9、10，需要切割成长度为4的成品30个；长度为5的成品20个；长度为7的成品40个。求解切割方案，使得总体成本价最低。

首先枚举所有可能切法：

（2）建立模型：定义变量表示使用第j种切割方案的次数，表示第j种方案的成本，表示第j种方案生成第i种木材的数量（i=1,2,3），所有切割方案的集合为J。表示j方案下分别切出来尺寸为4、5、7的木材的个数，表示所需尺寸为4、5、7木材的最小个数。该问题表示如下：

 （1）求解目标：找到最好的方案组合，使价格最小。

2、列生成方法：

（1）初始化

在枚举出的14种方案中挑选较好（价格最低）的方案组合，即前三种方案：

（2）主问题

此时的主问题为：

基于初始化的方案求解，利用gurobi求出最佳方案组合：,即前三种方案分别使用15、20、40次，总成本为325， 表示生成这三种长度的木材的合理价格。

（3）子问题

节省成本：

 即找到一个新的方案，计算该方案较原始方案的节省成本（切出来的总价值-成本）。当节省的成本都小于等于0时，求解问题达到最优。由于原木材有三种：长度尺寸为9、14、16，所以可分解为三个子问题。

 子问题2求解出来的节省成本最大，加入到主问题中。

（4）迭代

求解新生成的主问题，直到主问题对应的三个子问题求解出来的节省成本都是负数，表明当前主问题的解已是最优解，停止计算并输出结果。

四、平台实现

基于以上求解步骤即思想，依靠Python语言，借助Pycharm平台和gurobi求解器，求解上述板材切割问题。部分代码如下（关注“运筹学”公众号→后台回复“列生成算法”即可获取完整代码）：

最终结果：

可以得到原问题的最优解为：,即采用第一种、第二种和第四种切割方案，使用次数分别为5、20、20，最小成本为305。

五、与单纯形法对比

1、区别

（1）在求解过程上：单纯形法需要计算所有非基变量的RC，而列生成算法通过巧妙构造子问题，让这一步不需要遍历所有变量，甚至都不需要知道一共有多少变量，只要能在每次迭代的时候生成一个或者多个变量，提升优化效果就可以了，通过不断加入新变量直到没有小于0的RC的变量来求得最优解。

（2）在适用范围上：与单纯形法相比，列生成算法可以求解变量很多的线性规划问题，也就是前面所说的大规模的线性规划问题。

2、联系

从本质上来讲，列生成算法就是单纯形法的一种形式，是用来求解线性规划问题的。此外，列生成算法在求解每个子问题时，需要用到单纯形法。

★ 在python中安装Gurobi的详细教程可以参考以下网址：

    https://blog.csdn.net/weixin_41596280/article/details/89112302

★ 列生成算法参考资料1：https://blog.csdn.net/Rivalsx/article/details/97448943

★ 列生成算法参考资料2：https://blog.csdn.net/u014090505/article/details/89019327

作者｜陈怡敏、曹贵玲
责编｜何洋洋
审核｜徐小峰