Instructor Fall 2016: Sriram Sankaranarayanan

Prerequisites

Calculus I,II + Algorithms + Linear Algebra.

Topics Covered

Roughly, we will cover the following topics (some of them may be skipped depending on the time available).

  • Linear Programming: Basics, Simplex Algorithm, and Duality.

  • Applications of Linear Programming: regression, classification and other engineering applications.

  • Integer Linear Programming: Basics, Branch-and-Bound, Cutting Plane Methods.

  • Combinatorial Optimization: Basics of approximation algorithms.

  • Network flow problems.

  • Interior point methods.

  • ID

    Date Topics Covered Book Sections
    1 Aug 22 Introduction to Optimization Not from Book
    2 Aug 24 Linear Programming Problems and Examples. ch. 1
    3 Aug 26 Simplex method: basics ch. 2
    4 Aug 29 Simplex algorithm: pivoting and termination. ch. 2
    5 Aug 31 Initialization and termination of Simplex ch. 2
    6 Sep 2 Degeneracy and degenerate dictionaries ch. 3
    7 Sep 5 Cycling and Bland's rule ch. 3
    8 Sep 7 Geometry of Simplex ch. 2 & 3
    9 Sep 9 Correctness & Complexity ch. 3
    10 Sep 12 Duality theory ch. 5
    11 Sep 14 Properties of the dual problem c h. 5
    12 Sep 16 Dual Simplex and Initialization ch . 5
    13 Sep 19 Simplex algorithm in matrix form ch. 6
    14 Sep 21 Revised Simplex method ch. 8
    15 Sep 23 Factored form of the basis ch. 8
    16 Sep 26 Sensitivity analysis ch. 7
    17 Sep 28 wrap up of Simplex and duality  
    18 Sep 30 Regression: norms and their properties ch. 12
    19 Oct. 3 Regression and classification problems ch. 12
    20 Oct. 5 Financial portfolio selection ch. 13
    21 Oct. 7 Options, derivatives and pricing ch. 13
    22 Oct. 10 Tentative Date for Midterm upto sep. 30 lecture
    23 Oct. 12 Integer Linear Programming See Slides
    24 Oct. 14 Branch-and-bound method Slides
    25 Oct. 17 Cutting Plane Method Slides
    26 Oct. 19 Wrap up of ILP methods  
    27 Oct. 21 Travelling Salesperson Problem  
    29 Oct. 24 Approximation Algorithms  
    30 Oct. 26 Interior Point Methods ch. 17
    31 Oct. 28 Newton Method ch. 18
    32 Nov. 2 Convergence Analysis ch. 18

Textbook

We will primarily use the textbook by Robert Vanderbei.

Robert J. Vanderbei. Linear Programming: Foundations and Extensions, 4th Edition.

(Available online through CU libraries for all CU students).