• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
【24h】

Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem

机译：针对无约束二次0-1最小化问题的改进的紧凑线性化

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

摘要

We present and compare three new compact linearizations for the quadratic 0-1 minimization problem, two of which achieve the same lower bound as does the "standard linearization". Two of the linearizations require the same number of constraints with respect to Glover's one, while the last one requires n additional constraints where n is the number of variables in the quadratic 0-1 problem. All three linearizations require the same number of additional variables as does Glover's linearization. This is an improvement on the linearization of Adams, Forrester and Glover (2004) which requires n additional variables and 2n additional constraints to reach the same lower bound as does the standard linearization. Computational results show however that linearizations achieving a weaker lower bound at the root node have better global performances than stronger linearizations when solved by Cplex.
机译：我们针对二次0-1最小化问题提出并比较了三个新的紧凑线性化，其中两个实现了与“标准线性化”相同的下界。相对于Glover的线性化，两个线性化需要相同数量的约束，而最后一个线性化需要n个附加约束，其中n是二次0-1问题中的变量数量。这三个线性化都需要与Glover线性化相同数量的附加变量。这是对Adams，Forrester和Glover（2004）的线性化的改进，该线性化需要n个其他变量和2n个其他约束才能达到与标准线性化相同的下界。计算结果表明，当由Cplex求解时，在根节点处实现较弱的下限的线性化具有比较强的线性化更好的全局性能。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号