Instructor: Hemanshu Kaul

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

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

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

• Thursday, 4/8 : Exam #2 is two weeks away. See below for syllabus, etc.
  Also, the deadline for completion of Math 535 project is only 3 weeks away.
• Tuesday, 3/2 : HW # 7 has been uploaded.
• Thursday, 2/18 : Exam #1 is two weeks away. Also, the deadline for Math 535 project is only 10 days away.
• Tuesday, 1/14 : HW#1 has been uploaded.
• Tuesday, 1/12 : Check this webpage regularly for homework assignments, announcements, etc.

• Exam # 1 : Thursday, March 4th . Topics: Based on topics covered up to and including Thursday, February 18th [total 12 lectures].
• Exam # 2 : Thursday, April 22nd . Topics: Based on topics covered from and including February 23th and up to and including Thursday, April 8th [total 11 lectures].
• Final Exam : Tuesday, May 4, 10:30am - 12:30pm. Topics: Everything done during the semester.

• 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 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 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/21. Solutions distributed on 1/26, Tuesday.


• Tuesday, 1/19 : Read and understand proof of Theorem 2.1 from Section 2.1.
• Homework #2. Due Thursday, 1/28. Solutions distributed on 1/28, Thursday.


• Thursday, 1/28 : Read and understand the definition and example of Degenerate basic solutions from Section 2.4 on page 59. We will discuss it on Tuesday.
• 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/4. Solutions distributed on 2/4, Thursday.


• Homework #4. You can use MAPLE/MATLAB etc. for calculations if needed (please specify whenever used). Due Thursday, 2/11. Solutions distributed on 2/11, Thursday.


• Thursday, 2/11 : Read and understand Examples 3.5 and 3.6.
• Homework #5. You can use Calculator/MAPLE/MATLAB etc. for calculations if needed (please specify whenever used). Due Thursday, 2/18. Solutions distributed on 2/18, Thursday.


• Thursday, 2/18 : Read and understand Examples 3.8 and 3.9 from section 3.5.
• 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/25. Solutions distributed on 2/25, 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, BT 4.10. Due Thursday, 3/18.Solutions distributed on 3/23, Tuesday.


• Thursday, 3/18 : Read details of Examples 4.8 and 4.9 from Section 4.5. Read the details of Example 5.3 from Section 5.1.
• Homework #8 : SUBMIT one of {BT 4.21, BT 4.26}, BT 4.27, BT 5.5abde. Due Thursday, 3/25.Solutions distributed on 3/25, Thursday.


• Thursday, 3/27 : Read the details of Example 5.2 from section 5.1.
• Homework #9 : SUBMIT BT 5.1, BT 5.4 (B(delta) is B+delta.E, see BT 5.2), BT 5.13, BT 5.14abc. Due Thursday, 4/1. Solutions distributed on 4/6, Tuesday.


• Thursday, 4/11 : 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/8. Solutions distributed on 4/8, Thursday.


• Thursday, 4/8 : 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/15. Solutions distributed on 4/15, Thursday.


• Tuesday, 4/13 : Read and understand Example 10.3 from section 10.1.
• Thursday, 4/15 : 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/29. Solutions distributed on 4/29, Thursday.

• Tuesday, 1/12 : Linear Program and its various forms, Basic terminology, Matrix and vector forms for setting up an LP, Linear and Affine Functions, Dummy example to setup as LP, Setting up the Transportation problem as an LP. (From Section 1.1 and elsewhere)
• Thursday, 1/14 : 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, Linear-fractional programming problem as an LP. (From Sections 1.1, 1.4, 1.5, and elsewhere)
• Tuesday, 1/19 : Converting an optimization problem with a piecewise linear objective function into an LP, Removing absolute value function from an optimization 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/21 : Convex Hull is a convex set, Definition and geometric intuition of extreme point, vertex, and Basic feasible solution of a polyhedron, and the proof of their equivalence, active constraints, linear independence of constraints, properties of n active constraints, basic solutions (and their possible infeasibility). (From Section 2.2)
• Tuesday, 1/26 : Completion of 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 and how it can be used construct basic solutions for an standard form LP. (From Sections 2.2 and 2.3)
• Thursday, 1/28 : Characterization of basic solutions of a standard form Polyhedron and how it can be used to construct basic solutions for an standard form LP (we used facts about row-rank and column ranks of a matrix, and completion of a basis from Linear Algebra), 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. (From Sections 2.2 and 2.3)
• Tuesday, 2/2 : 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), If a standard LP has an optimal solution then it has an optimal BFS. (From Sections 2.4, 2.5, 2.6)
• Thursday, 2/4 : 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/9 : 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, An example, Optimality conditions for a Basis, 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/11 : Discussion on how many steps the Simplex algorithm can take to 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, 3.3, 3.7)
• Tuesday, 2/16 : 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, 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. (From Sections 3.3, 3.4, and elsewhere)
• Thursday, 2/18 : 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, How rank(A) strictly less than m implies a zero row in B^{-1}A in the final tableau of Phase1 which leads to removal of a redundant constraint, Several Examples illustrating the Two Phase Method, Big-M method. (From Section 3.5)
• Tuesday, 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. (From Sections 4.1 and 4.2)
• Thursday, 2/25 : Weak Duality Theorem 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. (From Section 4.3)
• Tuesday, 3/2 : 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, 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. (From Sections 4.3 and 4.5)
• Thursday, 3/4 : EXAM # 1. Exam #1 solutions distributed on 3/18, Thursday.
• Tuesday, 3/16 : 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 and its proof using strong duality. (From Sections 4.5 and 4.6)
• Thursday, 3/18 : 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, change in requirement vector; and how to handle such change. Distribution of Exam#1 and discussion of student performance. (From Sections 4.6 and 5.1)
• Tuesday, 3/23 : Discussion of change in feasibility and optimality of current optimal basis and BFS when - a new inequality constraint is added, 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/25 : Discussion of change in feasibility and optimality of current optimal basis and BFS when - change in cost vector, an entry in A is changed; and how to handle such change, Applying simplex algorithm to solve a parametric LP, Global dependence of optimal cost on requirement vector b. (From Sections 5.1, 5.5 and 5.2)
• Tuesday, 3/30 : 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, the delayed column generation problem as a knapsack problem. (From Sections 5.2, 5.4, 5.5, 6.1, 6.2)
• Thursday, 4/1 : 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/6 : 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/8 : 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 to add to the constraints, its relation to D-W decomposition, discussion of 2-stage stochastic LPs. (From Section 6.5, and elsewhere)
• Tuesday, 4/13 : Mixed Integer programs and their formulations - using binary variables to model various scenarios, examples, detailed example of formulation of an MIP for sequencing problem with setup times, LP relaxation, its relation to the IP and its optimal solution. (From Sections 10.1 and 10.2)
• Thursday, 4/15 : Cutting plane methods, Gomory cutting planes - proof of correctness, with an example, 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, a detailed IP example to illustrate the Branch and bound method for solving IPs including the use of bounds to prune the enumeration tree. (From Sections 10.2, 11.1, and 11.2)
• Tuesday, 4/20 : 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), Rewriting the Lagrangean dual as a linear program. (From Sections 11.2 and 11.4)
• Thursday, 4/22 : EXAM # 2. Exam #2 solutions distributed on 4/27, Tuesday.
• Tuesday, 4/27 : 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. Distribution of Exam#1 and discussion of student performance. (From Section 11.4)
• Thursday, 4/29 : [Not a part of the Final Exam Syllabus] Approximation algorithms, Randomized Algorithms, MAX SAT problem, 1/2-approx and (1-1/e)-approx randomized algorithms for MAX SAT, Randomized rounding technique through LP relaxation. (From Sections 11.5 and elsewhere)