47-779 course syllabus - Fall 2020

Weeks of August 31st and September 7th / Week 1

Integer programming classical methods

Integer Programming basics

Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, et al. Integer programming, volume 271. Springer, 2014.

Cutting plane theory and relaxations

Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, et al. Integer programming, volume 271. Springer, 2014.

Introduction to Test Sets

• Bernd Sturmfels.Grobner bases and convex polytopes, volume 8. American Mathematical Soc., 1996.
• Sridhar R Tayur, Rekha R Thomas, and NR Natraj. An algebraic geometry algorithm for scheduling in presence of setups and correlated demands. Mathematical Programming, 69(1-3):369–401, 1995.

Groebner basis

• Dimitris Bertsimas, Georgia Perakis, and Sridhar Tayur. A new algebraic geometry algorithm for integer programming. Management Science, 46(7):999–1008, 2000.
• Serkan Hosten and Bernd Sturmfels. Grin: An implementation of Grobner bases for integer programming. In International Conference on Integer Programming and Combinatorial Optimization, pages 267–276. Springer, 1995.

Graver Basis

• Raymond Hemmecke, Shmuel Onn, and Robert Weismantel. A polynomial oracle-time algorithm for convex integer minimization. Mathematical Programming, 126(1):97–117, 2011.