Breaking symmetries to rescue Sum of Squares in the case of makespan scheduling

Victor Verdugo, José Verschae, Andreas Wiese

The Sum of Squares (\sos{}) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for…