branch and price算法的原理解析是怎样的
本篇文章给大家分享的是有关branch and price算法的原理解析是怎样的，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。
相信大家对branch and price的神秘之处也非常好奇了。今天我们一起来揭秘该算法原理过程。
不过，在此之前，请大家确保自己的branch and bound和column generation的知识务必过关，而且是非常熟悉的那种。
因为branch and price算法就是branch and bound和column generation的结合体。
应用背景
branch and price算法就是branch and bound和column generation的结合体。具体是怎么结合的呢？先看一张BP的算法流程图，相信大家会清晰很多:
具体流程
我们知道branch and bound求解整数规划的过程，如果不知道看看下面这张图回顾一下：
在该过程中，定界的操作是通过求解当前问题的线性松弛(LP relaxation)得到的。对于一个变量很多的大规模整数规划问题而言，其线性松弛(LP relaxation)变量无疑也是非常多的。但在每一个节点中， 并不需要每一次都完完整整调用一次column generation，重新构建一次RMP再求解。 分子以后子节点的RMP可以直接将父节点的RMP挪过来，只不过由于加了分支约束，此时RMP需要重新添加column，再次求解以便得到最优。 而子节点的RMP重新添加column，再次求解的过程就是节点的bound操作了。那么，将以上的元素综合起来，就形成了我们的branch and price算法。
以上就是branch and price算法的原理解析是怎样的，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注行业资讯频道。
