|
|
Frank de Meijer (Tilburg University) - A cutting plane augmented Lagrangian method to solve SDP relaxations of the Quadratic Cycle Cover Problem Supervisor: Renata Sotirov Recorded full presentation Abstract 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. 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, whereas most state-of-the-art SDP solvers show poor performance in solving these type of relaxations. Computational results show that our SDP bounds and our efficient cutting plane algorithm outperform other QCCP bounding approaches from the literature. |
