1.文章信息

題目：An iterative dynamic programming approach for the temporal knapsack problem

作者：F.Clautiaux，B.Detienne，G.Guillot

來(lái)源：European Journal of Operational Research

出版信息：Volume 293, Issue 2, 1 September 2021, Pages 442-456

網(wǎng)址：https://doi.org/10.1016/J.EJOR.2020.12.036

2.文章導(dǎo)讀

背包問(wèn)題(Knapsack Problem)是組合優(yōu)化領(lǐng)域內(nèi)經(jīng)典的NP完全問(wèn)題，問(wèn)題可以描述為給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，如何選擇才能使得物品的總價(jià)格最高。該問(wèn)題的名稱來(lái)源于如何選擇最合適的物品放置于給定背包中，相似問(wèn)題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學(xué)，計(jì)算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中，其在資金分配、貨物裝載、項(xiàng)目選擇等問(wèn)題上有著廣泛的應(yīng)用。

3.摘要

本文討論了時(shí)間背包問(wèn)題（Temporal Knapsack Problem，TKP），這是經(jīng)典背包問(wèn)題的一個(gè)推廣，其中每個(gè)選定項(xiàng)都有一個(gè)時(shí)間窗口，可以在固定t時(shí)間進(jìn)入和離開背包，并且在每個(gè)時(shí)間段都考慮了容量約束。本文使用狀態(tài)空間指數(shù)大小的動(dòng)態(tài)程序?qū)?/span>TKP進(jìn)行建模，使用狀態(tài)和轉(zhuǎn)換來(lái)描述動(dòng)態(tài)程序，該動(dòng)態(tài)程序的工作原理基于事件概念，并且在狀態(tài)中添加了冗余信息（容量消耗），該程序使用連續(xù)升華動(dòng)態(tài)規(guī)劃（Successive Sublimation Dynamic Programming，SSDP）的方法進(jìn)行求解，該方法基于狀態(tài)空間松弛概念，對(duì)大量維數(shù)的動(dòng)態(tài)規(guī)劃問(wèn)題求解有著顯著的效果，其首先松弛初始問(wèn)題的一組約束，并在需要時(shí)重新引入松弛約束，直到達(dá)到最優(yōu)性證明。此外，由于SSDP方法需要很長(zhǎng)的計(jì)算時(shí)間來(lái)建立第一個(gè)松弛，計(jì)算第一個(gè)松弛時(shí)會(huì)生成許多無(wú)用的狀態(tài)等問(wèn)題，將SSDP直接應(yīng)用于時(shí)間背包問(wèn)題并不能得到有效的方法，故本文提出了幾種先進(jìn)的算法技術(shù)，顯著改善計(jì)算結(jié)果，并將其與商業(yè)MIP求解器進(jìn)行了實(shí)證比較。

4.主要內(nèi)容

時(shí)間背包問(wèn)題對(duì)于每個(gè)選定項(xiàng)都有一個(gè)時(shí)間約束，可以在固定t時(shí)間進(jìn)入和離開背包，并且在每個(gè)時(shí)間段都考慮了容量約束。圖1表示具有三項(xiàng)的TKP實(shí)例及其兩個(gè)包含最大解。在考慮容量約束和時(shí)間約束的情況下，沒有任何解決方案可以同時(shí)包含項(xiàng)目2和3，因?yàn)樗鼈冊(cè)跁r(shí)間3都處于活動(dòng)狀態(tài)，并且它們的大小之和大于容器的容量。

本文首先介紹了新混合整數(shù)規(guī)劃（Mixed Integer Programming，MIP）模型，其決策與時(shí)間窗口開始、結(jié)束事件相關(guān)。對(duì)于每個(gè)事件e，本文定義了一個(gè)二進(jìn)制變量，該變量指示是否執(zhí)行與事件e相關(guān)的操作。如果e屬于E-in中，該決定對(duì)應(yīng)于將與e相關(guān)的項(xiàng)目添加到當(dāng)前解決方案中，如果e屬于E-out，該決策對(duì)應(yīng)于刪除與e相關(guān)的項(xiàng)目。本文的動(dòng)態(tài)程序的工作原理與新MIP模型相似，也是基于新MIP模型使用的事件概念，并且在狀態(tài)中添加了冗余信息（容量消耗）。

本文使用狀態(tài)和轉(zhuǎn)換來(lái)正式描述動(dòng)態(tài)程序，將狀態(tài)變量定義為元組（e，w，d），其中e∈{1，…，2n+1}是當(dāng)前事件，w是當(dāng)前背包容量的消耗，d∈{0，1}n則是背包中當(dāng)前項(xiàng)集的特征向量，并將轉(zhuǎn)換（狀態(tài)轉(zhuǎn)移方程）稱為通過(guò)作出決定從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的可能性，轉(zhuǎn)換由元組（△e，△w，△d，p）定義，△e表示當(dāng)前事件的指數(shù)增加，△w是做出決策時(shí)消耗/釋放的背包容量，△d是更新背包內(nèi)容的向量，p是采取該決策時(shí)獲得的利潤(rùn)?？梢圆扇〉目赡軟Q策由ψ（允許決策集合）定義，ψ是將每個(gè)狀態(tài)與一組可行躍遷相關(guān)聯(lián)的函數(shù)，對(duì)于任何可行狀態(tài)（e，w，d），函數(shù)ψ（（e，w，d））計(jì)算如下：

每個(gè)狀態(tài)（e，w，d）的代價(jià)函數(shù)α（最優(yōu)指標(biāo)函數(shù)）以向后遞歸的方式表示，顯然，TKP的最佳值為α（（1，0，0）），其逆序遞推方程為

動(dòng)態(tài)程序的圖表示如圖2所示，在與輸出事件相關(guān)的層中，頂點(diǎn)只有一個(gè)輸出弧，而在與輸入事件相關(guān)的層中，最多有兩個(gè)可能的輸出弧。通過(guò)建立動(dòng)態(tài)規(guī)劃的圖形表示，從而找到與初始狀態(tài)相關(guān)聯(lián)的頂點(diǎn)和與最終狀態(tài)相關(guān)聯(lián)的頂點(diǎn)之間的最大利潤(rùn)路徑來(lái)解決問(wèn)題。

由于本文研究的動(dòng)態(tài)程序的狀態(tài)空間大小與二元向量d數(shù)量成指數(shù)關(guān)系，其大小為O(n×2n)，如上圖2所示，二元向量d的數(shù)量為3，則該狀態(tài)空間的大小即為24，該問(wèn)題屬于大量維數(shù)的動(dòng)態(tài)規(guī)劃問(wèn)題，故采用基于狀態(tài)空間松弛概念的SSDP方法進(jìn)行求解。SSDP是一種對(duì)偶方法，迭代求解將狀態(tài)空間松弛應(yīng)用于動(dòng)態(tài)程序而產(chǎn)生的問(wèn)題。SSDP的初始松弛是通過(guò)松弛導(dǎo)致狀態(tài)空間大小為指數(shù)大小的約束獲得的，通過(guò)求解松弛得到第一個(gè)對(duì)偶界，再通過(guò)重新定義松弛（即重新引入約束）來(lái)改進(jìn)該對(duì)偶界，直到與已知原始界的對(duì)偶間隙閉合，即原始界與對(duì)偶界趨于相等。通過(guò)如果弧a的上界低于問(wèn)題的已知下界，則弧a和相關(guān)轉(zhuǎn)換不能出現(xiàn)于松弛的最優(yōu)解中這一原理，在算法的每個(gè)步驟中，可以識(shí)別出一些不必要的狀態(tài)和轉(zhuǎn)換，并從后續(xù)松弛中刪除。

由于SSDP方法需要很長(zhǎng)的計(jì)算時(shí)間來(lái)建立第一個(gè)松弛，計(jì)算第一個(gè)松弛時(shí)會(huì)生成許多無(wú)用的狀態(tài)，并且在升華階段一次僅重新引入一個(gè)約束時(shí)，間隙不會(huì)顯著減小。所以對(duì)TKP直接應(yīng)用SSDP方法無(wú)法產(chǎn)生與最先進(jìn)的TKP求解器相似的理想結(jié)果，故本研究通過(guò)將附加信息附加到狀態(tài)、可行性測(cè)試、選擇要重新引入的約束的標(biāo)準(zhǔn)等方法解決這些問(wèn)題，從而提高SSDP求解TKP的性能。

最后，本文將實(shí)驗(yàn)結(jié)果與Gschwind和Irnich（2017）的結(jié)果以及使用通用商業(yè)整數(shù)線性規(guī)劃求解器獲得的結(jié)果進(jìn)行了比較。結(jié)果表明，Gschwind和Irnich（2017）的方法在較短的計(jì)算時(shí)間內(nèi)更有效，而SSDP在較長(zhǎng)的計(jì)算時(shí)間（＞1小時(shí)）方面表現(xiàn)優(yōu)異；與通用MILP求解器的比較得知，在三小時(shí)后解決的實(shí)例中，SSDP顯示出最佳性能。但對(duì)于大多數(shù)實(shí)例，如編號(hào)為1到55，SSDP花費(fèi)的時(shí)間可能較長(zhǎng)。

5.結(jié)論

本文提出了一種求解時(shí)間背包問(wèn)題的新算法，它基于狀態(tài)空間為指數(shù)大小的動(dòng)態(tài)程序，該規(guī)劃使用SSDP方法有效求解，該方法首先松弛初始問(wèn)題的一組約束，并在需要時(shí)重新引入松弛約束，直到達(dá)到最優(yōu)性證明。由于對(duì)TKP直接應(yīng)用SSDP方法無(wú)法產(chǎn)生與最先進(jìn)的TKP求解器相似的理想結(jié)果，故本研究通過(guò)將附加信息附加到狀態(tài)、可行性測(cè)試、選擇要重新引入的約束的標(biāo)準(zhǔn)等方法提高SSDP求解TKP的性能，從而達(dá)到理想的計(jì)算結(jié)果。

6.貢獻(xiàn)

1、該研究提出了一種求解時(shí)間背包問(wèn)題的新算法；

2、本研究提出了一種基于連續(xù)升華動(dòng)態(tài)規(guī)劃算法的求解方法；

3、數(shù)值實(shí)驗(yàn)表明，本研究提出的新穎算法在一定程度上優(yōu)于通用商業(yè)整數(shù)線性規(guī)劃求解器。

7.展望

本文提出的策略受許多參數(shù)的影響，更好的參數(shù)化可以產(chǎn)生更好的結(jié)果，這也是未來(lái)的關(guān)注方向之一；最關(guān)鍵的因素是在每個(gè)升華階段添加的約束條件的選擇，機(jī)器學(xué)習(xí)算法可以作為一種選擇，既可以微調(diào)提出的方法，也可以以更一般化的方式指導(dǎo)約束的選擇。