• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >The multi-band robust knapsack problem-A dynamic programming approach
【24h】

The multi-band robust knapsack problem-A dynamic programming approach

机译：多频带鲁棒背包问题-动态规划方法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we consider the multi-band robust knapsack problem which generalizes the Gamma-robust knapsack problem by subdividing the single deviation band into several smaller bands. We state a compact ILP formulation and develop two dynamic programming algorithms based on the presented model where the first has a complexity linear in the number of items and the second has a complexity linear in the knapsack capacity. As a side effect, we generalize a result of Bertsimas and Sim on combinatorial optimization problems with uncertain objective. A computational study demonstrates that the second dynamic program is significantly faster than the first algorithm, especially after application of further algorithmic ideas. The improved algorithm clearly outperforms CPLEX solving the compact ILP formulation. (C) 2015 Elsevier B.V. All rights reserved.
机译：在本文中，我们考虑了多频带鲁棒背包问题，该问题通过将单个偏差带细分为几个较小的频带来推广Gamma鲁棒背包问题。我们陈述了一个紧凑的ILP公式，并根据所提出的模型开发了两种动态规划算法，其中第一种算法的项数复杂度为线性，第二种算法的背包容量为线性。作为副作用，我们将Bertsimas和Sim的结果推广到具有不确定目标的组合优化问题。计算研究表明，第二个动态程序比第一个算法明显更快，尤其是在应用了其他算法思想之后。改进的算法明显优于CPLEX解决紧凑的ILP公式的性能。 （C）2015 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号