quadratic cycle cover problem – Optimization Online

SDP-based bounds for the Quadratic Cycle Cover Problem via cutting plane augmented Lagrangian methods and reinforcement learning

Published: 2020/09/08, Updated: 2021/02/18

Combinatorial Optimization, Semi-definite Programming cutting planes, dykstra's projection algorithm, facial reduction, quadratic cycle cover problem, reinforcement learning, semidefinite programming

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 … Read more

The Quadratic Cycle Cover Problem: special cases and efficient bounds

Published: 2019/04/04, Updated: 2019/11/30

Frank de Meijer

Renata Sotirov

Combinatorial Optimization equivalent representations, gilmore-lawler bound, linearization problem, quadratic cycle cover problem

The quadratic cycle cover problem is the problem of finding a set of node-disjoint cycles visiting all the nodes such that the total sum of interaction costs between incident arcs is minimized. In this paper we study the linearization problem for the quadratic cycle cover problem and related lower bounds. In particular, we derive various … Read more