{
  "id": "1902.05345",
  "version": "v1",
  "published": "2019-02-14T13:24:10.000Z",
  "updated": "2019-02-14T13:24:10.000Z",
  "title": "A Bundle Approach for SDPs with Exact Subgraph Constraints",
  "authors": [
    "Elisabeth Gaar",
    "Franz Rendl"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "The 'exact subgraph' approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into two independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Computational experiments on the Max-Cut, stable set and coloring problem show the efficiency of this approach.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-02-14T13:24:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C22",
      "90C27"
    ],
    "keywords": [
      "exact subgraph constraints",
      "bundle approach",
      "np-hard graph optimization problems",
      "increasingly tight semidefinite programming relaxations",
      "computational"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}