...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
【24h】

Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method

机译：通过紧凸重新构造提高二次0-1程序的标准求解器的性能：QCR方法

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

摘要

Let (QP) be a 0-1 quadratic program which consists in minimizing a quadratic function subject to linear equality constraints. In this paper, we present QCR, a general method to reformulate (QP) into an equivalent 0-1 program with a convex quadratic objective function. The reformulated problem can then be efficiently solved by a classical branch-and-bound algorithm, based on continuous relaxation. This idea is already present in the literature and used in standard solvers such as CPLEX. Our objective in this work was to find a convex reformulation whose continuous relaxation bound is, moreover, as tight as possible. From this point of view, we show that QCR is optimal in a certain sense. State-of-the-art reformulation methods mainly operate a perturbation of the diagonal terms and are valid for any {0, 1} vector. The innovation of QCR comes from the fact that the reformulation also uses the equality constraints and is valid on the feasible solution domain only. Hence, the superiority of QCR holds by construction. However, reformulation by QCR requires the solution of a semidefinite program which can be costly from the running time point of view. We carry out a computational experience on three different combinatorial optimization problems showing that the costly Computational time of reformulation by QCR can however result in a drastically more efficient branch-and-bound phase. Moreover, our new approach is competitive with very specific methods applied to particular optimization problems.
机译：令（QP）为0-1二次程序，该程序包含最小化受线性等式约束的二次函数。在本文中，我们介绍了QCR，这是将（QP）重新格式化为具有凸二次目标函数的等效0-1程序的通用方法。然后，可以基于连续松弛，通过经典的分支定界算法有效地解决重新构造的问题。这个想法已经存在于文献中，并用于标准求解器（例如CPLEX）中。我们在这项工作中的目标是找到一个凸的重构，其连续弛豫范围也要尽可能紧密。从这个角度来看，我们表明QCR在某种意义上是最佳的。最新的重构方法主要操作对角项的扰动，并且对任何{0，1}向量均有效。 QCR的创新来自这样一个事实，即重新制定也使用等式约束，并且仅在可行解域上有效。因此，QCR的优势在于结构。但是，通过QCR进行重新配方需要解决半确定程序，从运行时间的角度来看，这可能会导致成本高昂。我们对三个不同的组合优化问题进行了计算经验，结果表明，通过QCR进行重新计算的代价高昂的计算时间可能导致分支定界阶段的效率大大提高。而且，我们的新方法与针对特定优化问题的非常具体的方法相比具有竞争力。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号