CSE 190 - Discrete and Continuous Optimization

Syllabus

  1. What is linear programming?
  2. Linear programming formulations
  3. Integer programming and relaxations
  4. Linear programming theory
  5. Simplex method
  6. Duality
  7. Applications
  8. Continuous optimization

Textbooks

  1. Understanding and using linear programming, Jiri Matousek and Bernd Gärtner (accessible with UC San Diego credentials)
  2. Linear Programming Lecture Notes by Christopher Griffin
  3. Linear and nonlinear programming, David Luenberger and Yinyu Ye, 4th edition, Springer
  4. Linear and nonlinear programming, David Luenberger and Yinyu Ye, 3rd edition, Springer

Reading

  1. Weeks 1 and 2: Chapters 1 and 2 of Matousek and Gärtner; Chapters 1, 2, and 4 of Griffin
  2. Week 3: Chapter 4 of Griffin; Notes on convexity; Chapter 4 of Matousek and Gärtner
  3. Week 4: Chapters 4 and 5 of Matousek and Gärtner
  4. Weeks 5, 6, and 7: Chapters 2, 3, and 6 of Matousek and Gärtner
  5. 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

  1. Solving linear programs by hand
  2. Properties of feasible regions
  3. Formulating linear programs
  4. Linear programs in canonical form
  5. Simplex method
  6. Duality

Supplementary Reading

  1. Algorithms by Dasgupta, Papadimitriou, and Vazirani
  2. Understanding machine learning: From theory to algorithms
  3. Linear programming solution types
  4. Perceptron Classifiers (Charles Elkan)
  5. Understanding and using linear programming, Jiri Matousek and Bernd Gärtner (accessible with UC San Diego credentials)
  6. Approximation algorithms and semidefinite programming, Bernd Gärtner
  7. Introduction to linear optimization, Bertsimas, Tsitsiklis, and Tsitsiklis
  8. Linear and integer programming, Vince Conitzer
  9. Applied mathematical programming, Bradley, Hax, and Magnanti
  10. Introduction to optimization: Models and Methods, a course at Harvard University
  11. Combinatorial optimization, Cook, Cunningham, Pulleyblank, and Schrijver
  12. Combinatorial algorithms: theory and algorithms, Bernhard Korte and Jens Vygen
  13. Operations Research Models and Methods, Paul Jensen, Jonathan Bard