Conference 2021
Top image

Program LNMB conference
Invited Speakers
PhD student pitches
Return to LNMB Site

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

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.