...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >The inverse {0, 1}-knapsack problem: Theory, algorithms and computational experiments
【24h】

The inverse {0, 1}-knapsack problem: Theory, algorithms and computational experiments

机译：{0，1}-背包反问题：理论，算法和计算实验

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

摘要

The inverse {0,1}-knapsack problem consists of finding a minimal adjustment of the profit vector such that a given feasible set of items becomes an optimal solution. In this paper, two models are considered. In the first, the adjustment is measured by the Chebyshev norm. A pseudo-polynomial time algorithm is proposed to solve it. In the second, the adjustment is based on the Manhattan norm. This model is reduced to solve a linear integer program. While the first problem is proved to be co-NP-Complete, the second is co-NP-Hard and strong arguments are against its co-NP-Completeness. For both models, a bilevel linear integer programming formulation is also presented. Numerical results from computational experiments to assessing the feasibility of these approaches are reported.
机译：{0,1}-背包逆问题包括找到利润矢量的最小调整，以使给定的可行项目集成为最优解。本文考虑了两种模型。首先，调整是根据切比雪夫（Chebyshev）规范进行的。提出了一种伪多项式时间算法。第二，调整是基于曼哈顿规范。简化该模型以求解线性整数程序。虽然第一个问题被证明是co-NP-Complete，但第二个问题是co-NP-Hard，有力的论点反对它的co-NP-Completeness。对于这两个模型，还提出了双层线性整数规划公式。报告了从计算实验到评估这些方法的可行性的数值结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号