Sums-of-squares integer programming relaxation: Lecture 4

by Massimo Lauria

Lecture 4: Semidefinite program relaxations of integer programs.

Scribe: Mariette Annergren


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]