运筹学教学|列生成(Column Generation)算法(附代码及详细注释)

列生成算法

(Column Generation)

01

列生成算法的背景

多年来,寻找大规模的、复杂的优化问题的最优解一直是决策优化领域重要的研究方向之一。列生成算法通常被应用于求解大规模整数规划问题的分支定价算法(branch-and-price algorithm)中,其理论基础是由Danzig等于1960年提出。当求解一个最小化问题时,列生成算法主要的作用是为每个搜索树节点找到一个较优的下界(lower bound)。本质上而言,列生成算法就是单纯形法的一种形式,是用来求解线性规划问题的。列生成算法已被应用于求解如下著名的NP-hard优化问题:机组人员调度问题(Crew Assignment Problem)、切割问题(Cutting Stock Problem)、车辆路径问题(Vehicle Routing Problem)、单资源工厂选址问题(The single facility location problem )等。

02

列生成算法的基本思想

在某些线性优化问题的模型中,约束的数目有限,但是变量的数目随着问题规模的增长会爆炸式的增长,因此不能把所有的变量都显性的在模型中表达出来。在用单纯形法求解这类线性规划问题时,基变量(basic variable)只与约束的个数相关,每次迭代只会有一个新的非基变量(non-basic variable)进基,因此,在整个求解过程中其实只有很少一部分变量会被涉及到。简单来说,列生成算法通过求解子问题(pricing problem),来找到可以进基的非基变量,该非基变量在模型中并没有显性的写出来(可以看成是生成了一个变量,每个变量其实等价于一列,所以该方法被称为列生成算法)。如果找不到一个可以进基的非基变量,那么就意味着所有的非基变量的检验数(reduced cost)都满足最优解的条件,也就是说,该线性规划的最优解已被找到,即使很多变量没有在模型中写出来。

03

列生成算法实例——板材切割问题

(Cutting Stock Problem)

注意:留言处会给出一个链接,通过该链接读者可以下载本推文相关的书籍、课件、源程序以及算例。

3.1问题描述

木材厂卖木材,某顾客需要25根3英尺的木材、20根5英尺的木材和15根9英尺的木材,木材厂通过切17英尺的木材来满足顾客的需求。为了尽量减少木材的浪费,可以用线性规划方法来实现这个目标,同时用列生成来解这个线性规划问题。

3.2切割方案

切割过程中,木材厂要确定木材的切割方案(cutting combination)。举例说明,一根17英尺的木材可以切成3根5英尺的,这种切割方案将造成2英尺木材的浪费,实际过程中有很多种可能的切割方案,但是不合理的切割方案不需要被考虑。例如,只把17英尺木材切成一根9英尺,然后扔掉8英尺的方案明显不合理,因为我们可以把它切成一根9英尺、5英尺和3英尺的木材。总的来说,任何一种切割方案浪费木材量超过3英尺,我们都认为是不合理的,因为可以用浪费的木材去获得一根或多根3英尺的木材。不合理的切割方案不会在最优解中出现,因此不需要考虑。根据以上规则,我们可以枚举出以下六种切割方案。

04

代码实例

(来自cplex内置实例代码—Java版)

算例1:

17

[3,5,9]

[25,20,15]

结果1:

Best integer solution uses 19.0 rolls

Cut0 = 0.0

Cut1 = 1.0

Cut2 = 0.0

Cut3 = 15.0

Cut4 = 3.0

Solution status: Optimal

算例2:

5600

[1380,1520,1560,1710,1820,1880,1930,2000,2050,2100,2140,2150,2200]

[22,25,12,14,18,18,20,10,12,14,16,18,20]

结果2:

Best integer solution uses 73.0 rolls

Cut0 = 0.0

Cut1 = -0.0

Cut2 = -0.0

Cut3 = 1.0

Cut4 = -0.0

Cut5 = -0.0

Cut6 = -0.0

Cut7 = -0.0

Cut8 = -0.0

Cut9 = -0.0

Cut10 = -0.0

Cut11 = -0.0

Cut12 = -0.0

Cut13 = -0.0

Cut14 = -0.0

Cut15 = -0.0

Cut16 = 7.0

Cut17 = -0.0

Cut18 = -0.0

Cut19 = -0.0

Cut20 = 4.0

Cut21 = -0.0

Cut22 = 3.0

Cut23 = -0.0

Cut24 = -0.0

Cut25 = 5.0

Cut26 = -0.0

Cut27 = -0.0

Cut28 = 15.0

Cut29 = 3.0

Cut30 = 8.0

Cut31 = -0.0

Cut32 = 6.0

Cut33 = 9.0

Cut34 = 2.0

Cut35 = 7.0

Cut36 = 3.0

Solution status: Optimal

列生成(Column Generation)教学笔记到此结束!

本文代码引自 IBM ILOG CPLEX 内置的板材切割问题(cutstock)的源代码,小编做了详细的注释!

如果大家对 列生成算法及文中所叙内容还有疑问或想要交流心得建议,欢迎移步留言区!

END

编辑:黄楠(huangnanhust@163.com)

齐浩洋(895714656@qq.com )

指导老师:秦时明岳(professor.qin@qq.com)

感谢您,支持学生们的原创热情!

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2017-11-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吉浦迅科技

关于在Jetson TX2跑的那些深度学习的例子

Lady我总结了NVIDIA官方论坛推荐的几个在Jetson TX2跑的例子/教程,供各小主儿们学习。

2883
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列十二:多尺度的图像细节提升。

无意中浏览一篇文章,中间提到了基于多尺度的图像的细节提升算法,尝试了一下,还是有一定的效果的,结合最近一直研究的SSE优化,把算法的步骤和优化过程分享给大家。...

2398
来自专栏素质云笔记

LSH︱python实现MinHash-LSH及MinHash LSH Forest——datasketch(四)

关于局部敏感哈希算法,之前用R语言实现过,但是由于在R中效能太低,于是放弃用LSH来做相似性检索。学了Python发现很多模块都能实现,而且通过随机投影森林让查...

6906
来自专栏数据结构与算法

Kruskal重构树入门

在运行Kruskal算法的过程中,对于两个可以合并的节点$(x, y)$,断开其中的连边,并新建一个节点$T$,把$T$向$(x, y)$连边作为他们的父亲,同...

1865
来自专栏专知

【重磅】深度学习顶会 ICLR 2018 匿名提交论文列表(附pdf下载链接)

【导读】ICLR,全称为「International Conference on Learning Representations」(国际学习表征会议),201...

62810
来自专栏人人都是极客

【免费教学】Tensorflow Lite极简入门

边缘计算时代离我们越来越近,当前嵌入式设备的智能框架还是 TensorFlow Lite比较成熟,这里我准备用一系列免费课程和大家一起讨论下 TensorFlo...

2212
来自专栏owent

2018年的新通用伪随机数算法(xoshiro / xoroshiro)的C++(head only)实现

前段时间看到说Lua 5.4用了一种新的通用随机数算法,替换掉本来内部使用的CRT的随机数引擎。我看了一下大致的实现,CPU和空间复杂度任然保持了一个较低的水平...

1492
来自专栏安富莱嵌入式技术分享

【安富莱二代示波器教程】第10章 示波器设计—数字信号处理

本章节为大家讲解二代示波器中用到的FFT和FIR。单纯从应用上来说,比较省事,调用API函数即可,从学习的角度来说,需要大家花点精力。

933
来自专栏Petrichor的专栏

opencv: cv2.resize 探究(源码)

  我们 习惯的坐标表示 是 先 x 横坐标,再 y 纵坐标。在图像处理中,这种惯性思维尤其需要担心。

5033
来自专栏Spark学习技巧

复习:聊聊hive随机采样①

数据量大的时候,对数据进行采样,然后再做模型分析。作为数据仓库的必备品hive,我们如何对其进行采样呢?

1803

扫码关注云+社区