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

Time: 5pm-6:15pm, Monday and Wednesday.
Place: Pritzker Science Cntr 129.
Office Hours: Monday and Wednesday at 12pm-1pm. And by appointment in-person or through Zoom (send email).

TA Office Hours: Alaittin Kirtisoglu, Monday and Wednesday 3:30pm-5pm at RE 129 or through Zoom link at Math Tutoring Center.

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


• Thursday, 1/11 : This webpage will be updated every Thursday unless otherwise announced.


• Monday, 1/8 : Check this webpage regularly for homework assignments, announcements, etc.

• Exam #1 : Wednesday, February 21st. Syllabus: Based on topics, examples, and problems corresponding to HWs #1-#5.
• Exam #2 : Wednesday, April 10th. Syllabus: Based on topics, examples, and problems corresponding to HWs #6-#10.
• Final Exam : Monday, April 29th, 5-7pm, at PS 240. 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 - Matching/ Assignment problem as 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 Wednesday, 1/17, by 11pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #2 : 1 Lecture and 1 Holiday.
  
  • Topics: 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.
    • HW#2 for Submission. Due Wednesday, 1/24, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard 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. ]
      Ask for help during the instructor and TA office hours, or through email to the instructor.
      


• Week #3 : 2 Lectures.
  
  • Topics: 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), The proof of equivalence of extreme point, vertex, and BFS. (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.
    • HW#3 for Submission. Due Wednesday, 1/31, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard 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.]
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #4 : 2 Lectures.
  
  • Topics: 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, Characterization of basic solutions of a standard form Polyhedron and how it can be used to construct basic solutions for an standard form LP, Example 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.
    • HW#4 for Submission. Due Wednesday, 2/6, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard 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).
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #5 : 2 Lectures.
  
  • Topics: Theorem that shows why we can assume all rows of A are linearly independent, Proof of "Characterization of basic solutions of a standard form Polyhedron". 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 Monday). (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/15, by 11am in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      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: 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 Wednesday, 2/28, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #8 : 2 Lectures.
  
  • Topics: 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)
    Next week, a discussion of efficiency of Simplex Algorithm - worst case analysis and average case analysis versus smoothed analysis (see references in Reading HW below to learn more about this).
    
  • 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.
    • HW#7 for Submission. Due Wednesday, 3/6, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      BT 3.14, BT 3.17, BT 3.18cd, BT3.20abc. Also think about but don't submit: BT 3.24.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Weeks #9 and #10 : 2 Lectures and 2 Spring Break holidays.
  
  • Topics: Discussion of Exam 1 grades, score distribution, and solutions.
    Using Lagrangean relaxation (Lagrange multiplier method) to define a dual LP that maximizes a lower bound on the optimal cost of the primal LP, General rules for formulating a dual of a minimization - the relation between the constraints and variables/ rows and columns of these two LPs, Dual(Dual(Primal))= Primal, Duals of two equivalent LPs are also equivalent, Weak Duality Theorem. Weak Duality Theorem - proof and how it allows to check for optimality using a feasible solution of the dual, Strong Duality Theorem and how the optimal solution of the dual is defined using the optimal solution of the primal in standard form, Nine possibilities for the solution of a primal and its dual. (From Sections 3.5, 4.1, 4.2, 4.3, 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: Try but don't submit BT 4.1.
      Read and understand Table 4.2 and Example 4.6 from Section 4.3.
    • HW#8 for Submission. Due Wednesday, 3/20, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      [Math 435 students submit 4 out of 5, Math 535 submit all 5 problems]
      BT 4.2, BT 4.4, BT 4.5abc, BT 4.7, BT 4.8.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #11 : 2 Lectures.
  
  • Topics: Discussion of Exam 1 solutions completed.
    Weak Duality Theorem - proof and how it allows to check for optimality using a feasible solution of the dual, Strong Duality Theorem and how the optimal solution of the dual is defined using the optimal solution of the primal in standard form, Nine possibilities for the solution of a primal and its dual, Complementary slackness theorem and how is can be used to check whether a feasible solution of the primal is optimal, Detailed example for application of complementary slackness, The underlying principles of primal simplex and dual simplex algo. Basic (but not necessarily feasible) solutions for primal and dual using a basis matrix, dual feasibility iff reduced costs are non-negative, the termination conditions for the dual simplex, pivoting rule for the dual simplex, Applying Dual simplex when Dual BFS is easily available like when the constraint vector of the primal is changed. (From Section 4.3 and 4.4)
    
  • 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 4.6 from Section 4.3.
      Read, with close attention to details, Examples 4.7, 4.8 and 4.9 from Section 4.5.
    • HW#9 for Submission. Due Wednesday, 3/27, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      BT 4.10, BT 4.11, BT 4.25, and
      Use Complementary Slackness to verify that (0,1.5,4.5) is an optimal solution of the Linear Program: max c^Tx s.t. Ax ≤ b, x ≥ 0, where c^T= (3,0,2), A = [1,1,1; 2,-1,1; 3,1,-1] (row-by-row), and b^T=(6,3,3).
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #12 : 2 Lectures.
  
  • Topics: Cone of vectors, geometric interpretation of Farkas' lemma using idea of positive projections. Farkas' Lemma and its proof using strong and weak duality - how to choose the dual LPs to set up the proof, A Farkas-Lemma-type theorem proved using strong and weak duality. (From Sections 4.5 and 4.6)
    Local Sensitivity Analysis: Discussion of change in feasibility and optimality of current optimal basis and BFS, and how to handle such change, when - a new variable is added; a new inequality constraint is added; a new equality constraint is added (two approaches), change in requirement vector, change in cost vector; an entry in A is changed. (From Section 5.1)
    
  • 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 details of Examples 5.1, 5.2, and 5.3 from Section 5.1.
      Read the short discussions on changes in c and in nonbasic column of A.
    • HW#10 for Submission. Due Thursday, 4/4, by 11am in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Math 435 submit a total of 4 problems as required below while Math 535 students submit all 5 problems.
      Math 435 students submit one of {BT 4.26, BT 4.27} while Math 535 students submit both. (Also think about (but don't submit) BT 4.21.)
      Submit all three of {BT 5.1, BT 5.5abde, BT 5.4 [Comment: B(delta) is B+delta.E, see BT5.2 for definition. Hint: Calculate [B(delta)]^-1 explicitly]}.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #13 and #14 : 3 Lectures and 1 Mid-term Exam.
  
  • Topics:Review for Mid-term Exam#2.
    Completion of Local Sensitivity Analysis: Discussion of change in feasibility and optimality of current optimal basis and BFS when - a new variable is added; a new inequality constraint is added; a new equality constraint is added (two approaches), change in requirement vector, change in cost vector; an entry in A is changed; and how to handle such change.
    Optimal cost function of a parametric LP, applying simplex algorithm to solve a parametric LP, An extra example to illustrate the application of dual simplex algo to solve a parametric LP with parameter in the requirement vector, read it!
    Dantzig-Wolfe Decomposition - standard form of LP suitable for decomposition, decomposition into a master problem using extreme points of the polyhedra associated with the disjoint sets of variables, why we don't need to find out the extreme points of polyhedra to solve the master problem, using revised simplex and delayed column generation by defining subproblems associated with each underlying polyhedra which automatically finds a negative reduced cost and generates the appropriate extreme point needed to generate the corresponding constraint column in the master LP. Detailed exposition of example 6.2 for computational application of D-W decomposition method.
    
  • 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 Example 6.2 from Section 6.4.
    • HW#11 for Submission. Due Wednesday, 4/17, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions to be distributed in class.
      Submit any 5 out the following 6 problems: BT 5.13 [Review page 159, section 4.5 with regard to uniqueness], BT 5.14ab, BT 6.2, BT 6.4, BT 6.6, BT 6.8.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #15 and #16 : 4 Lectures.
  
  • Topics:Detailed exposition of example 6.2 for computational application of D-W decomposition method. How to find the initial BFS for the master LP, generalization to t subproblems, computational experience, storage comparison between straightforward simplex and D-W decomposition method, Bounds for the optimal cost of the Dantzig-Wolfe master problem in terms of the optimal costs of the subproblems.
    Two-stage stochastic LP - motivation, mathematical description, and the block structure of the problem, elaborate example, Detailed derivation of Bender's Decomposition , underlying idea of Bender's Decomposition as delayed constraint generation for such problems, standard form of LP suitable for decomposition, decomposition into a master problem using extreme points of the fixed dual polyhedra, how the violated constraint is found. (From Sections 6.1, 6.2, 6.3, 6.4, 6.5, and elsewhere)
    Discussion of Exam#2 scores and problems.
    Mixed Integer programs and their formulations - using binary variables to model various scenarios, examples, The distance between the feasible integral solution closest to the optimal solution of LP relaxation and the optimal solution of the IP can be very large, Detailed example of formulation of an MIP for sequencing problem with setup times. LP relaxation, its relation to the IP and its optimal solution, Cutting plane methods, Gomory cutting plane, Branch and Bound, [Optional: Integer Programming duality from 11.4.]. (From Sections 10.1, 10.2, 11.1, 11.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 10.1, 10.2, and "Allocation of NSF Fellowships" from Section 10.1.
      [Optional] Read Example 11.2 from Section 11.1 as application of Gomory-cut Algo.
      [Optional] Read Examples 11.4 and 11.5 from Section 11.2 as further illustrations of Branch and Bound.
      [Optional] Students also encouraged to read Sections 11.3 on Dynamic programming, 11.5 on Approximation Algorithms, 11.6 on Local Search, and 11.7 on Simulated Annealing. All these topics were discussed informally in class at various times in the semester.
    • HW#12 for Submission. [Optional to submit; replaces one previous lower HW score.]
      Due Friday, 4/26, by 11pm in Blackboard. Submit a PDF file through Blackboard Assignment.
      BT 6.9, BT 6.11, BT 10.2, BT 10.5, BT 11.1acd.
      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.