...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Naval Research Logistics >Concise RLT Forms of Binary Programs: A Computational Study of the Quadratic Knapsack Problem
【24h】

Concise RLT Forms of Binary Programs: A Computational Study of the Quadratic Knapsack Problem

机译：二进制程序的简洁RLT形式：二次背包问题的计算研究

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

摘要

The reformulation-linearization technique (RLT) is a methodology for constructing tight linear programming relaxations of mixed discrete problems. A key construct is the multiplication of "product factors" of the discrete variables with problem constraints to form polynomial restrictions, which are subsequently linearized. For special problem forms, the structure of these linearized constraints tends to suggest that certain classes may be more beneficial than others. We examine the usefulness of subsets of constraints for a family of 0-1 quadratic multidimensional knapsack programs and perform extensive computational tests on a classical special case known as the 0-1 quadratic knapsack problem. We consider RLT forms both with and without these inequalities, and their comparisons with linearizations derived from published methods. Interestingly, the computational results depend in part upon the commercial software used.
机译：重构线性化技术（RLT）是一种构造混合离散问题的紧密线性规划松弛的方法。一个关键的构造是离散变量的“乘积因子”与问题约束相乘以形成多项式约束，然后对其进行线性化。对于特殊的问题形式，这些线性约束的结构倾向于表明某些类别可能比其他类别更有利。我们检查了0-1二次多维背包程序族的约束子集的有用性，并对称为0-1二次背包问题的经典特殊情况进行了广泛的计算测试。我们考虑具有和不具有这些不等式的RLT形式，以及它们与从已公开方法得出的线性化的比较。有趣的是，计算结果部分取决于所使用的商业软件。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号