Instructor: Hemanshu Kaul

Office: 125C, Engineering 1
Phone: (312) 567-3128
E-mail: kaul [at] math.iit.edu

Time: 10am, Tuesday and Thursday.
Place: 244, Engg. 1 Bldg.

Office Hours: 11:30am-12:30pm Tuesday, 12:30-1:30pm Thursday, walk-ins, and by appointment. Emailed questions are also encouraged.

• Tuesday, 2/28 : HW # 7 has been uploaded. It is due a week after the mid-term Exam#1.


• Tuesday, 1/17 : Dates for Mid-term Exams #1 and #2 and Final Exam (with a correction) have been announced. Look below in the appropriate section.


• Tuesday, 1/10 : Check this webpage regularly for homework assignments, announcements, etc.

• Exam # 1 : Thursday, March 1st . Syllabus: Based on topics covered up to and including Thursday, February 16th [total 12 lectures].
• Exam # 2 : Thursday, April 19th . Syllabus: Based on topics covered from and including February 21st and up to and including Thursday, April 5th [total 11 lectures].
• Final Exam : Wednesday, May 2, 8am - 10am. 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 possibility is to use the online Linear Algebra lecture notes. Focus on the chapters on: Systems of Equations and Matrices, and Vector Spaces. You can practice simple problems .
  
  The third option is to use theMIT linear algebra site and study at least the lectures 1-11 listed in the syllabus. You can also use their video lectures (focus on the first 11 lectures).
  
  Of course, feel free to consult with me on any of these topics that you have difficulty with. Stop by my office during office hours.



• Tuesday, 1/12 : Read and understand Examples from Section 1.2.


• Homework #1. Due Thursday, 1/19. Solutions distributed on 1/19, Thursday.


• Tuesday, 1/17 : Read and understand proof of Theorem 2.1 from Section 2.1.


• Homework #2. Due Thursday, 1/26. Solutions distributed on 1/31, Tuesday.


• Thursday, 1/26 : Read and understand the definition and example of Degenerate basic solutions from Section 2.4 on page 59.


• Homework #3 : SUBMIT BT 2.3 (only state (do not prove) an analog of Theorem 2.4), BT 2.10bcde, BT 2.16, BT 2.17. Due Thursday, 2/2. Solutions distributed on 2/2, Thursday.


• Homework #4. You can use MAPLE/MATLAB/MATHEMATICA etc. for calculations if needed (please specify whenever used) but you still have to show all the intermediate steps. Due Thursday, 2/9. Solutions distributed on 2/9, Thursday.


• Thursday, 2/9 : Before you start HW#5: Read and understand Examples 3.5 and 3.6.
• Homework #5. You can use Calculator/MAPLE/MATLAB/Mathematica etc. for calculations if needed (please specify whenever used) but you still have to show all the intermediate tableaux. Due Thursday, 2/16. Solutions distributed on 2/16, Thursday.


• Thursday, 2/16 : Read and understand Example 3.8 from section 3.5, and the examples for the 2-phase method in the lecture log below.
• Homework #6 : SUBMIT BT 3.14, BT 3.17, BT 3.18cd, BT3.20abc. Also think about (but don't submit) BT 3.24. Due Thursday, 2/23. Solutions distributed on 2/23, Thursday.


• Tuesday, 3/2 : Read and understand Example 4.6 from section 4.3.
• Homework #7 : SUBMIT BT 4.1, BT 4.2, BT 4.4, BT 4.5abc, BT 4.7, BT 4.8. Due Thursday, 3/8.Solutions distributed on 3/8, Thursday.


• Tuesday, 3/6 : Read details of Examples 4.8 and 4.9 from Section 4.5.


• Thursday, 3/8 : Read the details of Examples 5.1, 5.2, and 5.3 from Section 5.1.
• Homework #8 : SUBMIT BT 4.10, one of {BT 4.21, BT 4.26}, BT 4.27, BT 5.1, BT 5.5abde. Due Thursday, 3/15. Solutions distributed on 3/15, Thursday.


• Homework #9 : SUBMIT BT 5.4 (B(delta) is B+delta.E, see BT 5.2), BT 5.13 (Review page 159, section 4.5 with regard to uniqueness), BT 5.14abc. Due Thursday, 3/29. Solutions distributed on 3/29, Thursday.


• Thursday, 3/29 : For your knowledge, read the statements of Theorem 4.15 and Corollary 4.4, and the solution of Example 4.10, from Section 4.9.
  Read Example 6.2 from Section 6.4.
• Homework #10 : SUBMIT BT 5.9, BT 6.1, BT 6.2, BT 6.9. Due Thursday, 4/5. Solutions distributed on 4/5, Thursday.


• Tuesday, 4/3 : Read Example 6.2 from section 6.4 if you missed the class.
• Homework #11 : SUBMIT one of {BT 6.4, BT 6.5}, BT 6.6, BT 6.8, BT 6.11. Due Thursday, 4/12. Solutions distributed on 4/12, Thursday.


• Thursday, 4/12 : Read and understand Example 10.3 from section 10.1.
• Tuesday, 4/17 : Read Examples 11.4 and 11.5 from section 11.2 as further illustrations of Branch and Bound.


• Homework #12 : SUBMIT BT 10.2, BT 10.3, BT 10.5, BT 11.1 [Detailed Instructions- part a: use a calculator if you like; part b: list all the points in X and then show the CH in the figure; part c: show the final simplex tableau of the LP relaxation before you pick the first Gomory cut and then show final tableau for the LP which includes this cut and say what you would do next; part d: Its enough to draw the enumeration tree the way I drew in class and use a calculator to solve the intermediate LPs; part e : Use the statement of Theorem 11.4 to write the LP that finds Z_D but before that write convex hull of the respective set X algebraically; part f : optional], [Optional BT 11.13, attempt after Tuesday, you will need to use Theorem 11.4 for this]. Due Thursday, 4/26. Solutions to be distributed on 4/26, Thursday.

• Tuesday, 1/10 : Linear Program and its various forms, Basic terminology, Matrix and vector forms for setting up an LP, Linear and Affine Functions, Manufacturing example to setup as LP, Setting up the Transportation problem as an LP. (From Section 1.1 and elsewhere)
• Thursday, 1/12 : Distribution and Discussion of course structure and information. Standard form of LP, How to convert any LP into standard form, When are two LPs (or optimization problems) equivalent; 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.; Geometric description of feasibility set of an LP, Geometric method of solution using family of parallel lines perpendicular to c, the cost vector, Different possible solutions for an LP. (From Sections 1.1, 1.4, 1.5, and elsewhere)
• Tuesday, 1/17 : Converting an optimization problem with a piecewise linear objective function into an LP, Removing absolute value function from an optimization problem - two methods, Linear-fractional programming problem 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, Basic properties of convexity - Polyhedron and Convex Hull are convex, etc. (From Sections 1.3, 2.1, 2.2)
• Thursday, 1/19 : A polyhedron and a convex Hull is a convex set, Definition and geometric intuition of extreme point, vertex, and Basic feasible solution of a polyhedron, active constraints, linear independence of constraints, properties of n active constraints, basic solutions (and their possible infeasibility). (From Section 2.2)
• Tuesday, 1/24 : The proof of equivalence of extreme point, vertex, and BFS; finiteness of number of basic solutions, Adjacent basic solutions (and corresponding geometric intuition), Polyhedron in standard form, Characterization of basic solutions of a standard form Polyhedron. (From Sections 2.2 and 2.3)
• Thursday, 1/26 : 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, Theorem that shows why we can assume all rows of A are linearly independent, Degenerate and non-degenerate Basic solutions. (From Sections 2.2, 2.3, and 2.4)
• Tuesday, 1/31 : Degenerate and non-degenerate Basic solutions with examples and geometric intuition, Degenerate Basic solutions in standard form polyhedron, Proof of "Characterization of basic solutions of a standard form Polyhedron" (From Sections 2.4 and 2.3)
• Thursday, 2/2 : Non-empty polyhedron has an extreme point iff it does not contain a line (without proof) and its consequences for std. and bounded polyhedra, If a standard LP has an optimal solution then it has an optimal BFS, A local search algo for solving an Optimization problem, 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, Change in the value of cost function and the corresponding reduced cost, Reduced cost of a basic variable. (From Sections 2.5, 2.6, 3.1 and 3.2)
• Tuesday, 2/7 : Reduced cost of a basic variable, for a given feasible direction how to choose theta to maximize the step length, 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, Change of basis and the associated BFS after an iteration of the Simplex Algo, The five step iteration of the simplex algorithm and its termination after finite number of steps and the two possible ways in which it can terminate. (From Sections 3.1 and 3.2)
• Thursday, 2/9 : Optimality conditions for a Basis, Simplex Algorithm - termination after finite number of steps and the two possible ways in which it can terminate, 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. (From Sections 3.2 and 3.3)
• Tuesday, 2/14 : Two Detailed Examples of Full Tableau Simplex Algorithm, 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. (From Sections 3.3, 3.4, and elsewhere)
• Thursday, 2/16 : 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 ruleHow 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, Several Examples illustrating the Two Phase Method. (From Section 3.5 and elsewhere)
• Tuesday, 2/21 : 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, Several Examples illustrating the Two Phase Method. How to check for optimality (Motivation), Using Lagrangean relaxation (Lagrange multiplier method) to define a dual LP. (From Sections 3.5, 4.1 and elsewhere)
• Thursday, 2/23 : 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 - proof and how it allows to check for optimality using a feasible solution of the dual. (From Sections 4.2 and 4.3)
• Tuesday, 2/28 : 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, pivoting rule and the termination conditions for the dual simplex. (From Sections 4.3 and 4.5)
• Thursday, 3/1 : EXAM # 1.
• Tuesday, 3/6 : Lex. 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, An example for running the Dual simplex, the underlying properties of Dual LP - Basis to dual basic solution, feasibility of dual basic solution, active dual constraint, degeneracy of dual basic solution; example illustrating the geometry of the dual simplex, cone of vectors, geometric interpretation of Farkas' lemma using idea of positive projections, Farkas' Lemma. (From Sections 4.5 and 4.6)
• Thursday, 3/8 : Farkas' Lemma and its proof using strong duality, A Farkas-Lemma-type theorem proved using strong and weak duality, 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; and how to handle such change. (From Sections 4.6 and 5.1)
• Tuesday, 3/13 : Distribution of Exam#1 and discussion of student performance, and the solutions. Discussion of change in feasibility and optimality of current optimal basis and BFS when - a new equality constraint is added (two approaches), change in cost vector; and how to handle such change, with examples. (From Section 5.1)
• Thursday, 3/15 : Discussion of change in feasibility and optimality of current optimal basis and BFS when - change in requirement vector, an entry in A is changed; and how to handle such change, Applying simplex algorithm to solve a parametric LP, Example to illustrate the application of dual simplex algo to solve a parametric LP with parameter in the requirement vectorGlobal dependence of optimal cost on requirement vector b. (From Sections 5.1, 5.5 and 5.2)
• Tuesday, 3/27 : [Online Lecture Only] Global dependence of optimal cost on requirement vector b (convexity) and on cost vector c (concavity); Example to illustrate the application of dual simplex algo to solve a parametric LP with parameter in the requirement vector; the principle of delayed column generation, the cutting stock problem - setup, relaxation to LP, solution using revised simplex and delayed column generation. (From Sections 5.2, 5.4, 5.5, 6.1, 6.2)
• Thursday, 3/29 : Details of the solution of the cutting stock problem using revised simplex and delayed column generation - initial BFS, iteration, (Knapsack Problem) subproblem that calculates reduced cost and generates the corresponding constraint column; Delayed column generation with retained columns and how an optimal solution for a restricted LP can be optimal for the full LP, Cutting plane methods as delayed constraint generation - the geometric intuition & its relation to delayed column generation for the dual; 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. (From Sections 6.1, 6.2, 6.3, 6.4)
• Tuesday, 4/3 : Dantzig-Wolfe Decomposition - 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, 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, detailed exposition of example 6.2 for computational application of D-W decomposition method, Bounds for the optimal cost of the Dantzig-Wolfe master problem in terms of the optimal costs of the subproblems. (From Section 6.4)
• Thursday, 4/5 : Two-stage stochastic LP - elaborate example, mathematical description, and the block structure of the problem, underlying idea of Bender's Decomposition as delayed constraint generation for such problems, Detailed derivation of Bender's Decomposition -standard form of LP suitable for decomposition, decomposition into a master problem using extreme points of the fixed dual polyhedra, finding the initial relaxed master LP, using dual simplex algo to find the cutting plane/ violated constraint to add to the constraints, its relation to D-W decomposition. (From Section 6.5, and elsewhere)
• Tuesday, 4/10 : Wrap up of the discussion of Bender's decomposition and how the violate constraint is found; Mixed Integer programs and their formulations - using binary variables to model various scenarios, examples. (From Sections 10.1 and 10.2)
• Thursday, 4/12 : Detailed example of formulation of an MIP for sequencing problem with setup times, LP relaxation, its relation to the IP and its optimal solution, A example to illustrate that 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, Cutting plane methods, Gomory cutting planes. (From Sections 10.2, 11.1, and 11.2)
• Tuesday, 4/17 : Gomory cutting planes - proof of correctness, A detailed IP example to illustrate the Branch and bound method for solving IPs including the use of bounds to prune the enumeration tree, general description of B&B, Duality theory for IPs - Lagrangean relaxations and the associated optimal costs and their relation to the optimal cost of IP, Lagrangean dual and its optimal cost as a better lower bound for the optimal cost of the IP (Weak Duality for IP). (From Sections 11.2 and 11.4)
• Thursday, 4/19 : EXAM # 2.
• Tuesday, 4/24 : Lagrangean dual and its optimal cost as a better lower bound for the optimal cost of the IP (Weak Duality for IP), Rewriting the Lagrangean dual as a linear program with proof, Understanding how to apply this theorem to solve Lagrangean dual using properties of Convex Hull, describing Convex Hull of integer points in terms of linear constraints, relationship between optimal costs of the IP, Lag. dual, and the LP relaxation. (From Section 11.4)
• Thursday, 4/26 : Distribution of Exam#1, and discussion of solutions and student performance.