干货 | 10分钟带你掌握branch and price(分支定价)算法超详细原理解析

 

20192019

分支定界算法

从入门到跑路放弃

 

1

前言

 

干货 | 10分钟带你掌握branch and price(分支定价)算法超详细原理解析

 

相信大家对branch and price的神秘之处也非常好奇了。今天我们一起来揭秘该算法原理过程。

 

不过,在此之前,请大家确保自己的branch and bound和column generation的知识务必过关,而且是非常熟悉的那种。

 

因为branch and price算法就是branch and bound和column generation的结合体。

 

2

应用背景

 

干货 | 10分钟带你掌握branch and price(分支定价)算法超详细原理解析

branch and price算法就是branch and bound和column generation的结合体。具体是怎么结合的呢?先看一张BP的算法流程图,相信大家会清晰很多:

 

干货 | 10分钟带你掌握branch and price(分支定价)算法超详细原理解析

 

3

具体流程

 

干货 | 10分钟带你掌握branch and price(分支定价)算法超详细原理解析

 

我们知道branch and bound求解整数规划的过程,如果不知道看看下面这张图回顾一下:

 

干货 | 10分钟带你掌握branch and price(分支定价)算法超详细原理解析

 



在该过程中,定界的操作是通过求解当前问题的线性松弛(LP relaxation)得到的。对于一个变量很多的大规模整数规划问题而言,其线性松弛(LP relaxation)变量无疑也是非常多的。那么,这时候,我们上节课介绍的column generation就可以出马了。

 

但在每一个节点中,并不需要每一次都完完整整调用一次column generation,重新构建一次RMP再求解。分子以后子节点的RMP可以直接将父节点的RMP挪过来,只不过由于加了分支约束,此时RMP需要重新添加column,再次求解以便得到最优。而子节点的RMP重新添加column,再次求解的过程就是节点的bound操作了。那么,将以上的元素综合起来,就形成了我们的branch and price算法。

 

4

代码

 

目前没有相关的能够公开的代码,后续可能会写一下这个算法的,嗯肯定会写。可以关注公众号【程序猿声】获取第一时间的消息。

 

干货 | 10分钟带你掌握branch and price(分支定价)算法超详细原理解析

 

干货 | 10分钟带你掌握branch and price(分支定价)算法超详细原理解析

END

 

注:对文中或者代码有疑问可联系小编,可提供有偿辅导服务。

图片来源:网络(侵删)

扫码关注

更多精彩

 

上一篇:WDK李宏毅学习笔记第十五周01_Conditional Generation by Conditional


下一篇:1094 谷歌的招聘 (20 分)