Optimization Online


A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for some NP-Hard Graph Optimization Problems

Elspeth Adams(elspeth.adams***at***polymtl.ca)
Miguel F. Anjos(anjos***at***stanfordalumni.org)
Franz Rendl(rendl***at***aau.at)
Angelika Wiegele(angelika.wiegele***at***aau.at)

Abstract: Many important NP-hard combinatorial problems can be efficiently approximated using semidefinite programming relaxations. We propose a new hierarchy of semidefinite relaxations for classes of such problems that based on graphs and for which the projection of the problem onto a subgraph shares the same structure as the original problem. This includes the well-studied max-cut and stable-set problems. Each level $k$ of the proposed hierarchy consists of the basic semidefinite relaxation of the problem augmented by the constraints enforcing the structural projection condition on every $k$-node subgraph of the problem. This hierarchy has the distinguishing feature that all the relaxations are formulated in the space of the original semidefinite relaxation. Because the complexity of the relaxations increases rapidly with the number of subgraphs, we explore the possibility of adding the projection constraints only for selected subgraphs. Preliminary computational results show that the proposed hierarchy yields improved bounds when compared to the initial relaxation for benchmark instances of the max-cut and stable-set problems, and that the improved bounds result in significantly smaller enumeration trees when the relaxation is used in a branch-and-bound scheme.


Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Unpublished: Cahier G-2013-80, GERAD, November 2013.

Download: [PDF]

Entry Submitted: 11/27/2013
Entry Accepted: 11/27/2013
Entry Last Modified: 11/27/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society