Dynamic programming algorithms for the bi-objective integer knapsack problem
Dynamic programming algorithms for the bi-objective integer knapsack problem
复制标题
DOI：
10.1016/j.ejor.2013.11.032
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Aiying Rong;J. Figueira
中科院分区：
文献类型：
--
作者：
Aiying Rong;J. Figueira
针对双目标整数背包问题，提出了两种新的求解Pareto前沿的动态规划算法。首先，确定了多目标整数背包问题的传统DP算法的一个性质。第一个算法是直接利用该属性开发的。第二种算法是使用界集概念的混合DP方法。该属性与绑定集一起使用。接下来，数值实验表明，一个有前途的部分解决方案，有时可以被丢弃，如果与部分解决方案相关的子问题的线性松弛的解决方案直接用于估计的上限集。这意味着上界集被低估了。然后，在线性松弛解集的基础上，提出了一个扩展的上界集。通过收紧所提出的上界集合，提高了混合算法的效率。不同类型的双目标实例的数值结果表明了该方法的有效性。
This paper presents two new dynamic programming (DP) algorithms to find the exact Pareto frontier for the bi-objective integer knapsack problem. First, a property of the traditional DP algorithm for the multi-objective integer knapsack problem is identified. The first algorithm is developed by directly using the property. The second algorithm is a hybrid DP approach using the concept of the bound sets. The property is used in conjunction with the bound sets. Next, the numerical experiments showed that a promising partial solution can be sometimes discarded if the solutions of the linear relaxation for the subproblem associated with the partial solution are directly used to estimate an upper bound set. It means that the upper bound set is underestimated. Then, an extended upper bound set is proposed on the basis of the set of linear relaxation solutions. The efficiency of the hybrid algorithm is improved by tightening the proposed upper bound set. The numerical results obtained from different types of bi-objective instances show the effectiveness of the proposed approach.