dykstra’s projection algorithm

Partitioning through projections: strong SDP bounds for large graph partition problems

  • Frank de Meijer
  • Renata Sotirov
  • Angelika Wiegele
  • Shudian Zhao
    • Categories Semi-definite Programming Tags , , , ,

    The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both … Read more

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

  • Frank de Meijer
  • Renata Sotirov
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

    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