运筹说 第71期｜论文速读之时间背包问题

前几期的推送已经讲解了动态规划的基本知识、数学模型和相关算法，相信大家对动态规划已经有了充分的了解，这期小编将带大家一起来读一篇关于时间背包问题的迭代动态规划方法的文章。

1.文章信息

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

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

来源：European Journal of Operational Research

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

网址：https://doi.org/10.1016/J.EJOR.2020.12.036

2.文章导读

背包问题(Knapsack Problem)是组合优化领域内经典的NP完全问题，问题可以描述为给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，如何选择才能使得物品的总价格最高。该问题的名称来源于如何选择最合适的物品放置于给定背包中，相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中，其在资金分配、货物装载、项目选择等问题上有着广泛的应用。

3.摘要

本文讨论了时间背包问题（Temporal Knapsack Problem，TKP），这是经典背包问题的一个推广，其中每个选定项都有一个时间窗口，可以在固定t时间进入和离开背包，并且在每个时间段都考虑了容量约束。本文使用状态空间指数大小的动态程序对TKP进行建模，使用状态和转换来描述动态程序，该动态程序的工作原理基于事件概念，并且在状态中添加了冗余信息（容量消耗），该程序使用连续升华动态规划（Successive Sublimation Dynamic Programming，SSDP）的方法进行求解，该方法基于状态空间松弛概念，对大量维数的动态规划问题求解有着显著的效果，其首先松弛初始问题的一组约束，并在需要时重新引入松弛约束，直到达到最优性证明。此外，由于SSDP方法需要很长的计算时间来建立第一个松弛，计算第一个松弛时会生成许多无用的状态等问题，将SSDP直接应用于时间背包问题并不能得到有效的方法，故本文提出了几种先进的算法技术，显著改善计算结果，并将其与商业MIP求解器进行了实证比较。

4.主要内容

时间背包问题对于每个选定项都有一个时间约束，可以在固定t时间进入和离开背包，并且在每个时间段都考虑了容量约束。图1表示具有三项的TKP实例及其两个包含最大解。在考虑容量约束和时间约束的情况下，没有任何解决方案可以同时包含项目2和3，因为它们在时间3都处于活动状态，并且它们的大小之和大于容器的容量。

本文首先介绍了新混合整数规划（Mixed Integer Programming，MIP）模型，其决策与时间窗口开始、结束事件相关。对于每个事件e，本文定义了一个二进制变量，该变量指示是否执行与事件e相关的操作。如果e属于E-in中，该决定对应于将与e相关的项目添加到当前解决方案中，如果e属于E-out，该决策对应于删除与e相关的项目。本文的动态程序的工作原理与新MIP模型相似，也是基于新MIP模型使用的事件概念，并且在状态中添加了冗余信息（容量消耗）。

本文使用状态和转换来正式描述动态程序，将状态变量定义为元组（e，w，d），其中e∈{1，…，2n+1}是当前事件，w是当前背包容量的消耗，d∈则是背包中当前项集的特征向量，并将转换（状态转移方程）称为通过作出决定从一个状态转移到另一个状态的可能性，转换由元组（e，w，d，p）定义，e表示当前事件的指数增加，w是做出决策时消耗/释放的背包容量，d是更新背包内容的向量，p是采取该决策时获得的利润。可以采取的可能决策由ψ（允许决策集合）定义，ψ是将每个状态与一组可行跃迁相关联的函数，对于任何可行状态（e，w，d），函数ψ（（e，w，d））计算如下：

每个状态（e，w，d）的代价函数α（最优指标函数）以向后递归的方式表示，显然，TKP的最佳值为α（（1，0，0）），其逆序递推方程为

动态程序的图表示如图2所示，在与输出事件相关的层中，顶点只有一个输出弧，而在与输入事件相关的层中，最多有两个可能的输出弧。通过建立动态规划的图形表示，从而找到与初始状态相关联的顶点和与最终状态相关联的顶点之间的最大利润路径来解决问题。

由于本文研究的动态程序的状态空间大小与二元向量d数量成指数关系，其大小为O（n×），如上图2所示，二元向量d的数量为3，则该状态空间的大小即为24，该问题属于大量维数的动态规划问题，故采用基于状态空间松弛概念的SSDP方法进行求解。SSDP是一种对偶方法，迭代求解将状态空间松弛应用于动态程序而产生的问题。SSDP的初始松弛是通过松弛导致状态空间大小为指数大小的约束获得的，通过求解松弛得到第一个对偶界，再通过重新定义松弛（即重新引入约束）来改进该对偶界，直到与已知原始界的对偶间隙闭合，即原始界与对偶界趋于相等。通过如果弧a的上界低于问题的已知下界，则弧a和相关转换不能出现于松弛的最优解中这一原理，在算法的每个步骤中，可以识别出一些不必要的状态和转换，并从后续松弛中删除。

由于SSDP方法需要很长的计算时间来建立第一个松弛，计算第一个松弛时会生成许多无用的状态，并且在升华阶段一次仅重新引入一个约束时，间隙不会显著减小。所以对TKP直接应用SSDP方法无法产生与最先进的TKP求解器相似的理想结果，故本研究通过将附加信息附加到状态、可行性测试、选择要重新引入的约束的标准等方法解决这些问题，从而提高SSDP求解TKP的性能。

最后，本文将实验结果与Gschwind和Irnich（2017）的结果以及使用通用商业整数线性规划求解器获得的结果进行了比较。结果表明，Gschwind和Irnich（2017）的方法在较短的计算时间内更有效，而SSDP在较长的计算时间（＞1小时）方面表现优异；与通用MILP求解器的比较得知，在三小时后解决的实例中，SSDP显示出最佳性能。但对于大多数实例，如编号为1到55，SSDP花费的时间可能较长。

5.结论

本文提出了一种求解时间背包问题的新算法，它基于状态空间为指数大小的动态程序，该规划使用SSDP方法有效求解，该方法首先松弛初始问题的一组约束，并在需要时重新引入松弛约束，直到达到最优性证明。由于对TKP直接应用SSDP方法无法产生与最先进的TKP求解器相似的理想结果，故本研究通过将附加信息附加到状态、可行性测试、选择要重新引入的约束的标准等方法提高SSDP求解TKP的性能，从而达到理想的计算结果。

6.贡献

1、该研究提出了一种求解时间背包问题的新算法；

2、本研究提出了一种基于连续升华动态规划算法的求解方法；

3、数值实验表明，本研究提出的新颖算法在一定程度上优于通用商业整数线性规划求解器。

7.展望

本文提出的策略受许多参数的影响，更好的参数化可以产生更好的结果，这也是未来的关注方向之一；最关键的因素是在每个升华阶段添加的约束条件的选择，机器学习算法可以作为一种选择，既可以微调提出的方法，也可以以更一般化的方式指导约束的选择。