CSE 190  Discrete and Continuous Optimization
Syllabus
 What is linear programming?
 Linear programming formulations
 Integer programming and relaxations
 Linear programming theory
 Simplex method
 Duality
 Applications
 Continuous optimization
Textbooks
 Understanding and using linear programming, Jiri Matousek and Bernd Gärtner (accessible with UC San Diego credentials)
 Linear Programming Lecture Notes by Christopher Griffin
 Linear and nonlinear programming, David Luenberger and Yinyu Ye, 4th edition, Springer
 Linear and nonlinear programming, David Luenberger and Yinyu Ye, 3rd edition, Springer
Reading
 Weeks 1 and 2: Chapters 1 and 2 of Matousek and Gärtner; Chapters 1, 2, and 4 of Griffin
 Week 3: Chapter 4 of Griffin; Notes on convexity; Chapter 4 of Matousek and Gärtner
 Week 4: Chapters 4 and 5 of Matousek and Gärtner
 Weeks 5, 6, and 7: Chapters 2, 3, and 6 of Matousek and Gärtner
 Weeks 8, 9, and 10: Sections 6.1, 6.2 and 6.3 and 8.1 and 8.2 of Matousek and Gärtner
Problem Sets
 Solving linear programs by hand
 Properties of feasible regions
 Formulating linear programs
 Linear programs in canonical form
 Simplex method
 Duality
Supplementary Reading
 Algorithms by Dasgupta, Papadimitriou, and Vazirani
 Understanding machine learning: From theory to algorithms
 Linear programming solution types
 Perceptron Classifiers (Charles Elkan)
 Understanding and using linear programming, Jiri Matousek and Bernd Gärtner (accessible with UC San Diego credentials)
 Approximation algorithms and semidefinite programming, Bernd Gärtner
 Introduction to linear optimization, Bertsimas, Tsitsiklis, and Tsitsiklis
 Linear and integer programming, Vince Conitzer
 Applied mathematical programming, Bradley, Hax, and Magnanti
 Introduction to optimization: Models and Methods, a course at Harvard University
 Combinatorial optimization, Cook, Cunningham, Pulleyblank, and Schrijver
 Combinatorial algorithms: theory and algorithms, Bernhard Korte and Jens Vygen
 Operations Research Models and Methods, Paul Jensen, Jonathan Bard
