论文标题
通过切割飞机增强拉格朗日方法和增强学习的基于二次循环覆盖问题的基于SDP的界限
SDP-based bounds for the Quadratic Cycle Cover Problem via cutting plane augmented Lagrangian methods and reinforcement learning
论文作者
论文摘要
我们研究了二次循环覆盖问题（QCCP），该问题旨在在有向图中找到一个节点 - 分散循环覆盖范围，并在连续的弧线之间具有最低的相互作用成本。我们得出了几种半决赛编程（SDP）放松，并使用面部减少来使这些变得严格可行。我们研究了在还原和图的结构中使用的转换矩阵之间的非平凡关系，该矩阵在有效的算法中被利用，该算法构造了该矩阵的任何问题。为了解决我们的放松，我们提出了一种算法，该算法通过利用Dykstra的投影算法将增强的拉格朗日方法纳入切割平面框架中。我们的算法适用于用大量切割平面来解决SDP松弛。计算结果表明，我们的SDP界限和有效的切割平面算法优于文献中其他QCCP边界方法。最后，我们提供了几种基于SDP的上边界技术，其中一种顺序Q学习方法在增强学习环境中利用了我们的SDP松弛解决方案。
We study the Quadratic Cycle Cover Problem (QCCP), which aims to find a node-disjoint cycle cover in a directed graph with minimum interaction cost between successive arcs. We derive several semidefinite programming (SDP) relaxations and use facial reduction to make these strictly feasible. We investigate a nontrivial relationship between the transformation matrix used in the reduction and the structure of the graph, which is exploited in an efficient algorithm that constructs this matrix for any instance of the problem. To solve our relaxations, we propose an algorithm that incorporates an augmented Lagrangian method into a cutting plane framework by utilizing Dykstra's projection algorithm. Our algorithm is suitable for solving SDP relaxations with a large number of cutting planes. Computational results show that our SDP bounds and our efficient cutting plane algorithm outperform other QCCP bounding approaches from the literature. Finally, we provide several SDP-based upper bounding techniques, among which a sequential Q-learning method that exploits a solution of our SDP relaxation within a reinforcement learning environment.
