Instructor: Hemanshu Kaul
Office: Rettaliata Engg Cntr 125C.
E-mail: kaul [at] iit.edu

Time: 1:50pm-3:05pm, Tuesday and Thursday.
Place: Hermann Hall 003.
Office Hours: Tuesday at 12:30pm-1:30pm, and Thursday at 4:30pm-5:30pm. And by appointment in-person or through Zoom (send email).

TA Office Hours: Alaittin Kirtisoglu, Wednesday 2pm-5pm at RE 129 or through Math Tutoring Center.

• Thursday, 1/29 : Dates for Mid-term Exams #1 and #2 have been announced. Look below in the appropriate section. Mark your calendars.


• Thursday, 1/15 : This webpage will be updated every Thursday unless otherwise announced.
• Tuesday, 1/13 : Check this webpage regularly for homework assignments, announcements, etc.

• Exam #1 : Thursday, 2/26 . Syllabus: Based on topics, examples, and problems corresponding to HWs #1-#5.
• Exam #2 : Thursday, 4/16 . Syllabus: Based on topics, examples, and problems corresponding to HWs #6-#10.
• Final Exam : TBA by university . Syllabus: All topics covered during the semester.

• Homework #0
  Linear Algebra Background : Read and understand the Linear Algebra background (MATH 332 or its equivalent is a pre-requisite for this course) from Section 1.5 within the first 10 days of the semester.
  You need to be familiar with topics like - System of linear equations, Row operations for solving systems of linear equations, R^n as a vector space, Subspaces, Span, Linear Independence, Basis, Dimension, Nullspace of a matrix, Matrix rank, Affine subspaces.
  You can pick up any standard undergraduate linear algebra textbook from the IIT library, like Anton, Elementary Linear Algebra, 9th/ 10th ed. or Lay, Linear Algebra and its applications, 3rd ed., and follow along the topics covered in my IIT course at Math 332.
  Another option is to use the MIT linear algebra site and study at least the lectures 1-11 as given under video lectures.
  
  Of course, feel free to consult with me on any of these topics that you have difficulty with. Stop by during my office hours.


• Week #1 : 2 Lectures.
  
  • Topics and Readings: Discussion of the course; Linear Optimization as a tool for general-purpose modeling and general purpose optimization algorithms - Max Flow Problem as LP; Logistics and setting up the Transportation/ Min Cost Network Flow problem as an LP; Linear Program and its various forms, Basic terminology, Matrix and vector forms for setting up an LP, How to convert any LP into standard form. (From Sections 1.1, 1.2, and elsewhere)
    
  • Homework:
    The homeworks listed below are from the course textbook unless otherwise noted.
    Follow the detailed instructions and rules for HWs given in the Course Information Handout and through emailed comments.
    
    • Reading HW:
      Read and understand Examples from Section 1.2.
      Read the discussion on page 18 (Section 1.3).
    • Homework #1 for submission [PDF]. Due Thursday, 1/22, by 11pm in Canvas. Submit a single PDF file through Canvas Assignment. HW Solutions distributed in class.
      Questions? Ask on Canvas Discussion Forum. Or, Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #2 : 2 Lectures.
  
  • Topics and Readings: Why standard form? its relation to general solution of system of m linear equations in n variables, and the related concepts of Null space of A, nullity, rank, etc., When are two LPs (or optimization problems) equivalent? Converting an optimization problem with a piecewise linear objective function into an LP, Removing absolute value function from an optimization problem - two methods. Geometric method of solution using family of parallel lines perpendicular to c, the cost vector, Different possible solutions for an LP based on different cost functions. (From Sections 1.2, 1.3, 1.4, 1.5, and elsewhere)
    
  • Homework:
    The homeworks listed below are from the course textbook unless otherwise noted.
    Follow the detailed instructions and rules for HWs given in the Course Information Handout and through emailed comments.
    
    • Reading HW:
      Read the discussion on page 18 (Section 1.3).
      Read Section 1.8.
      Read the initial few pages of Section 2.1.
    • Homework #2 for submission. Due Thursday, 1/29, by 11pm in Canvas. Submit a single PDF file through Canvas Assignment. HW Solutions distributed in class.
      BT 1.4, BT 1.5ab, BT 1.6, BT 1.14.
      [Comment for 1.14: You should show a sketch in your solution to illustrate/justify the answer for part(c).]
      [Comment for 1.5b: Proving the following two statements is enough to finish the proof. You need to submit the proof of only ONE of these two statements. Below, P0 refers to the given optimization problem, P1 refers to the first reformulation, and P2 refers to the second reformulation.
      (i) Given a feasible solution of P0, find a feasible solution of P1 with cost no more than the cost in P0. And, given a feasible solution of P1, find a feasible solution of P0 with cost no more than the cost in P1.
      (ii) Given a feasible solution of P0, find a feasible solution of P2 with cost no more than the cost in P0. And, given a feasible solution of P2, find a feasible solution of P0 with cost no more than the cost in P2. ]
      Questions? Ask on Canvas Discussion Forum. Or, Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #3 : 2 Lectures.
  
  • Topics and Readings: Geometric definitions - Polyhedron, Polytope, Hyperplane, Half-space, A polyhedron is the intersection of half-spaces, Convexity of a set; Convex combination and Convex Hull of a finite set of vectors, A polyhedron is the intersection of half-spaces, Convex combination and Convex Hull of a finite set of vectors, properties of convex sets, a polyhedron and a convex Hull are convex sets. Definition and geometric intuition of extreme point and vertex. Basic Solution and Basic feasible solution of a polyhedron, active constraints, linear independence of constraints, Properties of n active constraints, basic solutions (and their possible infeasibility), Equivalence of extreme point, vertex, and BFS, Characterization of basic solutions of a standard form Polyhedron and how it can be used to construct basic solutions for an standard form LP. (From Sections 2.1 and 2.2)
    
  • Homework:
    The homeworks listed below are from the course textbook unless otherwise noted.
    Follow the detailed instructions and rules for HWs given in the Course Information Handout and through emailed comments.
    
    • Reading HW:
      Verify that the corner points in Example 1.6 of Section 1.4 satisfy the definitions of Extreme point, Vertex, and BFS.
    • Homework #3 for submission. Due Thursday, 2/5, by 11pm in Canvas. Submit a single PDF file through Canvas Assignment. HW Solutions distributed in class.
      BT 2.4 and construct an non-empty polyhedron with no extreme points, BT 2.6a, BT 2.10bcde, BT 2.16.
      [Comment: For all these problems assume that we have already proved that: Every non-empty polyhedron in the standard form has at least one extreme point.]
      Questions? Ask on Canvas Discussion Forum. Or, Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #4 : 2 Lectures.
  
  • Topics and Readings: The proof of equivalence of extreme point, vertex, and BFS. Adjacent basic solutions (and corresponding geometric intuition), Finiteness of number of basic solutions, Polyhedron in standard form, How to construct basic solutions for an standard form LP, Examples and definitions of basic variables, basic columns, basis matrix and using the basis matrix to solve for the basic variables and constructing a basic solution, More examples for constructing Basic solutions, Relation between Bases and Basic solutions, Adjacent basic solutions with examples (and corresponding geometric intuition). (From Sections 2.2 and 2.3)
    
  • Homework:
    The homeworks listed below are from the course textbook unless otherwise noted.
    Follow the detailed instructions and rules for HWs given in the Course Information Handout and through emailed comments.
    
    • Reading HW:
      Read first two pages of Section 2.4, including examples. We will also discuss this in class.
    • Homework #4 for submission. Due Thursday, 2/12, by 11pm in Canvas. Submit a single PDF file through Canvas Assignment. HW Solutions distributed in class.
      BT 2.1, BT 2.3 (State the procedure, and state, without proof, an analog of Theorem 2.4), BT 2.8, BT 2.9a (first finish the reading HW).
      Questions? Ask on Canvas Discussion Forum. Or, Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #5 : 2 Lectures.
  
  • Topics and Readings: Theorem that shows why we can assume all rows of A are linearly independent, Degenerate and non-degenerate Basic solutions with examples and geometric intuition, Degenerate Basic solutions in standard form polyhedron, Non-empty polyhedron has an extreme point iff it does not contain a line (without proof) and its consequences for standard and bounded polyhedra. If a standard LP has an optimal solution then it has an optimal BFS. Feasible direction, Analysis of how to choose direction d and step length theta to move from a current BFS to a new one - jth basic direction from equality constraints, How the choice of the step length (and feasible direction) implies that a basic variable becomes zero and leaves the basis while a non-basic variable becomes non-zero and enters the basis, Main steps of the Simplex Algo (to be completed with example on Tuesday). (From Sections 2.3, 2.4, 3.1 and 3.2)
    
  • Homework:
    The homeworks listed below are from the course textbook unless otherwise noted.
    Follow the detailed instructions and rules for HWs given in the Course Information Handout and through emailed comments.
    
    • Reading HW:
      Read and understand Example 3.1.
      Read "An Iteration of Simplex Method" on page 90-91.
    • Homework #5 for submission [PDF] Due Thursday, 2/19, by 11pm in Canvas. Submit a single PDF file through Canvas Assignment. HW Solutions distributed in class.
      Questions? Ask on Canvas Discussion Forum. Or, Ask for help during the instructor and TA office hours, or through email to the instructor.


• Weeks #6 and #7 : 3 Lectures and 1 mid-term Exam.
  
  • Topics and Readings: Change of basis and the associated BFS after an iteration of the Simplex Algo, Optimality conditions for a BFS, Optimal Basis, Reduced cost of basic variables, Example of calculation for five steps of a full iteration of Simplex Algorithm, Simplex Algorithm under degeneracy, the difference between moving from BFS to BFS and moving from Basis to Basis, Cycling and how it can be avoided, pivoting rules, Bland's rule, How to minimize the computations associated with running the simplex - particularly calculating the inverse of updated basis matrix, Full tableau form of Simplex Algo, Interpretation of the tableau entries and how they are updated using elementary row operations, Two Detailed Examples of Full Tableau Simplex Algorithm. (From Sections 3.2 3.3, 3.4, and elsewhere)
    
  • Homework:
    The homeworks listed below are from the course textbook unless otherwise noted.
    Follow the detailed instructions and rules for HWs given in the Course Information Handout and through emailed comments.
    
    • Reading HW:
      Read and understand Examples 3.5 and 3.6.
      Also read the tableau examples from the classroom, linked in the lecture log above.
    • Homework #6 for submission [PDF] Due Thursday, 3/5, by 11pm in Canvas. Submit a single PDF file through Canvas Assignment.
      Questions? Ask on Canvas Discussion Forum. Or, Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #8 : 2 Lectures.
  
  • Topics and Readings: Revised simplex algo and how its different from full tableau simplex, Difference between their number of operations and number of entries to maintain, Lexicographic order and Lex. pivoting rule, Why lex pivoting rule gives an unique pivot row, How to setup a tableau such that all the rows (except zeroth) are lex positive, Proof of why no cycling occurs when using lex pivoting rule. How to find an initial BFS for a standard form LP, Two phase method using artificial variables, The three possible conclusions of the Phase 1: positive optimal cost and why that implies infeasible original LP, zero optimal cost and no artificial variable in the basis, zero optimal cost and some artificial variables in the basis; How to remove artificial variables from the optimal basis of Phase 1 - linear independence of old basis columns from A and the new incoming basis column from A, Using Phase 1 to check for full rank of A and to check infeasibility of LP. Big-M method as an alternate to the two-phase method. Several Examples illustrating the Two Phase Method. (From Sections 3.3, 3.4, 3.5, and elsewhere)
    
  • Homework:
    The homeworks listed below are from the course textbook unless otherwise noted.
    Follow the detailed instructions and rules for HWs given in the Course Information Handout and through emailed comments.
    
    • Reading HW:
      
      • Read and understand Examples 3.8 and 3.9 from Section 3.5, and the examples for the 2-phase method in the lecture log above.
      • If interested, browse through Smoothed Analysis of Simplex Method that shows why its so efficient in practice: The seminal 2001 paper of Spielman and Teng, A magazine article on its discovery, A recent easier-to-follow survey of this idea over the past 18 years.
      • If interested, look up AMPL, GAMS, GLPK, CPLEX, and GUROBI for information about large scale computation of optimization models.
    • Homework #7 for submission. Due Thursday, 3/12, by 11pm in Canvas. Submit a single PDF file through Canvas Assignment.
      BT 3.14, BT 3.17, BT 3.18cd, BT3.20abc. Also think about but don't submit: BT 3.24.
      Questions? Ask on Canvas Discussion Forum. Or, Ask for help during the instructor and TA office hours, or through email to the instructor.

• LP book by Vanderbei
• H.P. Williams, Model Building in Mathematical Programming, Fifth Edition.
• Hillier and Lieberman, Introduction to Operations Research, 7th edition onwards.

• Linear Programming at Wikipedia
• OR Models
• NEOS Optimization Guide
• Mathematical Programming Glossary
• Mathworld-Optimization
• Myths and Counterexamples
• Look up AMPL, GAMS, GLPK, CPLEX, and GUROBI for information about large scale computation of optimization models.