溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關(guān)branch and price算法的原理解析是怎樣的，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說(shuō)，跟著小編一起來(lái)看看吧。
相信大家對(duì)branch and price的神秘之處也非常好奇了。今天我們一起來(lái)揭秘該算法原理過(guò)程。
不過(guò)，在此之前，請(qǐng)大家確保自己的branch and bound和column generation的知識(shí)務(wù)必過(guò)關(guān)，而且是非常熟悉的那種。
因?yàn)閎ranch and price算法就是branch and bound和column generation的結(jié)合體。
應(yīng)用背景
branch and price算法就是branch and bound和column generation的結(jié)合體。具體是怎么結(jié)合的呢？先看一張BP的算法流程圖，相信大家會(huì)清晰很多:
具體流程
我們知道branch and bound求解整數(shù)規(guī)劃的過(guò)程，如果不知道看看下面這張圖回顧一下：
在該過(guò)程中，定界的操作是通過(guò)求解當(dāng)前問(wèn)題的線性松弛(LP relaxation)得到的。對(duì)于一個(gè)變量很多的大規(guī)模整數(shù)規(guī)劃問(wèn)題而言，其線性松弛(LP relaxation)變量無(wú)疑也是非常多的。但在每一個(gè)節(jié)點(diǎn)中， 并不需要每一次都完完整整調(diào)用一次column generation，重新構(gòu)建一次RMP再求解。 分子以后子節(jié)點(diǎn)的RMP可以直接將父節(jié)點(diǎn)的RMP挪過(guò)來(lái)，只不過(guò)由于加了分支約束，此時(shí)RMP需要重新添加column，再次求解以便得到最優(yōu)。 而子節(jié)點(diǎn)的RMP重新添加column，再次求解的過(guò)程就是節(jié)點(diǎn)的bound操作了。那么，將以上的元素綜合起來(lái)，就形成了我們的branch and price算法。
以上就是branch and price算法的原理解析是怎樣的，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼
