• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >An exact solution method for quadratic matching: The one-quadratic-term technique and generalisations
【24h】

An exact solution method for quadratic matching: The one-quadratic-term technique and generalisations

机译：二次匹配的精确解法：单二次项技术和推广

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

摘要

The quadratic matching problem (QMP) asks for a matching in a graph that optimises a quadratic objective in the edge variables. The QMP generalises the quadratic assignment problem as the latter can be seen as a perfect matching on a bipartite graph. In our approach, we strengthen the linearised IP-formulation by cutting planes that are derived from facets of the corresponding matching problem where only one quadratic term is present in the objective function (QMP1). As the influence of these cutting planes on the root bound decreases for instances with more quadratic terms in the objective, we present different methods to strengthen these cutting planes. Adopting the idea of the reformulation linearisation technique (RLT) we derive valid inequalities for the general QMP from QMP1 facets. Following the approach in Fomeni et al. (2015) we replace cubic terms that appear in a reformulated QMP1 inequality by a quadratic estimator. Based on these methods we design and implement an exact branch-and-cut approach. When compared to solving the standard linearised IP formulation strengthened by cutting planes that result from the application of the RLT to the degree inequalities, we show that root bounds and cpu times for solving instances to optimality can significantly be improved, when the new method is applied. (C) 2015 Elsevier B.V. All rights reserved.
机译：二次匹配问题（QMP）要求在图中进行匹配，以优化边缘变量中的二次目标。 QMP概括了二次分配问题，因为后者可以看作是二分图上的完美​​匹配。在我们的方法中，我们通过切割平面来加强线性化IP公式，该平面是从对应匹配问题的方面中得出的，其中目标函数（QMP1）中仅存在一个二次项。由于在目标中具有更多二次项的情况下，这些切割平面对根边界的影响减小，因此，我们提出了不同的方法来增强这些切割平面。通过采用重构线性化技术（RLT）的思想，我们从QMP1方面推导了一般QMP的有效不等式。按照Fomeni等人的方法。 （2015年），我们用二次估计器代替了在重新形成的QMP1不等式中出现的三次项。基于这些方法，我们设计并实现了精确的分支剪切方法。与解决通过将RLT应用到度数不等式而得到的剖切面来增强标准的线性化IP公式进行求解相比，我们表明，当使用新方法时，可以极大地改善求解实例到最优性的根边界和cpu时间。 （C）2015 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号