lifting procedures

Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems

  • Miguel F. Anjos
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Semidefinite optimization, commonly referred to as semidefinite programming, has been a remarkably active area of research in optimization during the last decade. For combinatorial problems in particular, semidefinite programming has had a truly significant impact. This paper surveys some of the results obtained in the application of semidefinite programming to satisfiability and maximum-satisfiability problems. The … Read more

    Computing the stability number of a graph via linear and semidefinite programming

  • Javier F. Peña
  • Juan Vera
  • Luis F. Zuluaga
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We study certain linear and semidefinite programming lifting approximation schemes for computing the stability number of a graph. Our work is based on, and refines De Klerk and Pasechnik’s approach to approximating the stability number via copositive programming (SIAM J. Optim. 12 (2002), 875–892). We provide a closed-form expression for the values computed by the … Read more