Sums-of-squares integer programming relaxation: Lecture 4

by Massimo Lauria

Lecture 4: Semidefinite program relaxations of integer programs.

Scribe: Mariette Annergren

Abstract

We continue the discussion on how to improve the initial relaxation made of an integer program. Here, we focus on semidefinite program (SDP) relaxations, and we introduce Lovász-Schrijver relaxation with semidefinite programming, and the Positivstellensatz, Positivstellensatz Calculus and sums-of-squares (SOS) proof systems.

Link: [Lecture notes 04]

Advertisements