A computational study of exact subgraph based SDP bounds for Max-Cut, stable set and coloring

Area of Science:

• Computational mathematics
• Graph theory
• Operations research

Background:

• Semidefinite programming (SDP) relaxations offer hierarchical schemes for NP-hard graph optimization.
• Solving these relaxations is computationally intensive due to numerous subgraph constraints.

Purpose of the Study:

• To develop an efficient computational framework for SDP relaxations of NP-hard graph problems.
• To overcome the computational challenges associated with large numbers of violated subgraph constraints.

Main Methods:

• Introduction of a partial Lagrangian dual approach.
• Decomposition of the dual function evaluation into independent subproblems.
• Application of the bundle method from non-smooth optimization for dual function minimization.

Main Results:

• Demonstration of an effective computational framework for SDP relaxations.
• Successful application to Max-Cut, stable set, and coloring problems.
• Attainment of high-quality bounds for these NP-hard graph optimization problems.

Conclusions:

• The proposed computational framework effectively addresses the challenges of SDP relaxations.
• The partial Lagrangian dual and bundle method provide an efficient approach to obtain tight bounds.
• This method shows excellent performance for key graph optimization problems.