Welcome, this is the Web Page for the course 3006995 Linear Programming and Combinatorial Optimization (Undergraduate) and 300911 Linear Optimization and Combinatorics (Graduate). Here you will find:

1. Syllabus 3006995. Syllabus 300911

2. An update of the course content covered on a session-by-session basis.

3. The course will be lectured in English. Since English is not your native language you are strongly encouraged to read in advance the corresponding material.

4. Textbook and Reading Materials.

5. Homework Assignments.

6. Test Dates and Solutions.

7. Related Software Links.

8. Related online Journals Links.

9. Links to online Free Courses Related to Linear and Discrete Optimization.

10. Inspirational and Confusing unrelated material intended to push out-of-the-box thinking and free association of ideas.

1. May 7th, 2019. Presentation of the course, evaluation method and dynamics. Discussion of a variety of continuous optimization problems, convex and nonlinear.

2. May 9th, 2019. Discussion of convex functions. The diet problem, Section 1.1 in Reference 2. The job assignment problem (the matching problem), Section 1.2 in Reference 2. Linear algebra review, the row picture vs the column picture. Section 2.1 in Reference 5.

3. May 14th, 2019. Linear Algebra Review. Span, Linear Independence, Bases, Subspaces. Transpose of a matrix as an adjoint operator. The Dimension Theorem,. The four fundamental spaces associated to a matrix. Hyperplanes, linear affine spaces. From Reference 5. Homework 1, due May 28th. The Debate Session is scheduled for Monday 10:00 -12:00, room 43-226.

4. May 16th, 2019. All the material was taken from Reference 1. Affine hyperplanes and subspaces. Visualization of a feasible region in 2D, section 1.4. The General Form and the Standard Form of a linear optimization program (LOP), section 1.1. Reductions from one form to the other and back. A scheduling problem, pg 11. A pattern classification problem, pg 14. The Data Fitting problem pg 19, removing the absolute sense in the norms L_infinity and L_1, pg 17.

5. May 21st, 2019. All the material was taken from Reference 1. Summary of possibilities for linear optimization problems (LOP), pg 24. Counting matrix operations, dot product, matrix-vector and matrix-matrix, Definition 1.2, Section 1.6. Starting Chapter 2, The Geometry of Linear Programming. Definition 2.1, Definition 2.2, Definition 2.5, Theorem 2.1, Definition 2.6

6. May 23th, 2019. All the material was taken from Reference 1. Definitio 2.6 (review), Definition 2.7, Definition 2.8 (active/binding constraints). Theorem 2.2, Definition 2.9: Basic Solution and Basic Feasible Solution. Theorem 2.3 equivalence between vertex, extreme point and basic feasible solution.

7. May 28th, 2019. All the material was taken from Reference 1. Review of Theorem 2.3, Corollary 2.1. The unit cube case: 2n linear constraints define 2^n vertices; an example of how a linear number of constraints may define an exponential number of vertices. Adjacent basic solutions. , pg 53. Comments on Polyhedra in Standard form, Theorem 2.4, Example 2.1 (Section 2.3).

8. May 30th, 2019. All the material was taken from Reference 1. Theorem 2.4 review. When are two bases considered different, Basic Columns, Basic Variables and Nonbasic Variables, pg 55. Correspondence of Bases and Basic Solutions, pg 56. Adjacent Basic Solutions and Adjacent Bases, Example 2.2, pg 56. Theorem 2.5, Example 2.3. Degeneracy, Definition 2.10, several examples. Degeneracy in Standard Form Polyhedra, Definition 2.11. Degeneracy is not a Purely Geometric Property, Examples, pg 60. Existence of Extreme Points, Definition 2.1, Theorem 2.6 (incomplete).

9. June 4th, 2019. All the material was taken from Reference 1. Theorem 2.6 review and finished prove. Corollary 2.2 discussion. Theorem 2.7. Motivation behind Theorem 2.8

10. June 6th, 2019. All the material was taken from Reference 1. Theorem 2.8, Theorem 2.9. Problem Set II, available here.

11. June 11th, 2019. Suspended due to XXII Congreso Colombiano de Matemáticas.

12. June 13th, 2019. Suspended due to XXII Congreso Colombiano de Matemáticas.

13. June 18th, 2019. All the material was taken from Reference 1. Theorem 2.8, filling the gap. Section 2.8 the Fourier-Motzkin eliminination Algorithm, pages 70, 71, 72.. Theorem 2.10, Corollary 2.4, Corollary 2.5 and Corollary 2.6. First test scheduled for June the 29th.

14. June 20th, 2019. All the material was taken from Reference 1. Starting Chapter 3, THE SIMPLEX METHOD. Review of Polyhedra in Standard Form, basic and nonbasic variables. The index notation B(1), B(2), ..., B(k), x_B, B = [A_B(1), A_B(2), ..., A_B(k)]. The equality Ax = Bx_B = b for basic feasible solutions. Discussion of local minima vs global minima for convex functions on convex domains. Definition 3.1 for feasible directions. Computation of feasible directions, starting from a basic feasible solution x. Homework 2, due July 2nd, 2019.

15. June 25th, 2019. All the material was taken from Reference 1. Review of the index notation B(1), B(2), ..., B(k), x_B, B = [A_B(1), A_B(2), ..., A_B(k)]. The equality Ax = Bx_B = b for basic feasible solutions (pgs 82-83). Construction of feasible directions at a given basic feasible solution x. Computation of cost reduction rates, Definition 3.2, Example 3.1. Theorem 3.1.

16. June 27th, 2019. All the material was taken from Reference 1. Revisiting the construction of feasible directions d at a given basic feasible solution x. Definition 3.3. Development of the Simplex Method, Section 3.2, Theorem 3.2.

17. June 29th, 2019. FIRST TEST, you can download it HERE. You can work in groups, consult the textbook (Reference 1) and your class notes, however, every student shall submit and individual paper. Your papers are due June 30th at 0:00. Problem Set IV, available here.

18. July 2nd, 2019. All the material was taken from Reference 1. Revisiting Theorem 3.2, a simple example. An iteration of the Simplex Method, pags 90, 91. Theorem 3.3. The Simplex Method for Degenerate Problems, pg 92. Pivot Selection pgs 92, 93, 94. READING ASSIGNMENT, read from Section 3.3 Naive Implementation (pg 94), Revised Simplex Method (pgs 95, 96, 97). An Iteration of the Revised Simplex Method.

19. July 4th, 2019. All the material was taken from Reference 1. The Full Tableau Implementation, An Iteration of the Full Tableau Implementation, pgs 98, 99, 100, Example 3.5. Section 3.4, Lexicography pgs 108, 109, Definition 3.5, Lexicographical pivoting rule, Example 3.7, Theorem 3.4. HOMEWORK III, due July 23th, on coding and implementation. You can download the files Data_Generation.py , Vectors_0.xls and Vectors_1.xls by clicking on the links, the folder "Homework 3 Files" containing all the files, can be accessed through this link. The instruccions can be donloaded here. Problem Set IV, available here.

20. July 23th, 2019. All the material was taken from Reference 1. Section 3.5: Finding an initial BFS, Driving artificial variables out of the basis. The two phase simplex Method. Discussion about the meanings behind HW3.

21. July 25th, 2019. All the material was taken from Reference 1. Starting Chapter 4. Motivation of the Dual Problem: The Bounding Approach vs The Lagrange Multipliers Approach. Section 4.1, Section 4.2: Summary of page 142, Table 4.1, Example 4.1 and Theorem 4.1.

22. July 30th, 2019. All the material was taken from Reference 1. Starting Chapter 4. Example 4.2, Example 4.3, Theorem 4.2 on the equivalence of dual problems coming from equivalent forms. Theorem 4.3 (weak duality), Corollary 4.1 (infeasibility), Corollary 4.2 (certificates of optimality), Theorem 4.4 (strong duality). Second Test Scheduled for August the 10th at 7:00 am. HOMEWORK IV ready, Problems 2, 12 and 17, due August 10th, 2019.

23. August the 1st, 2019. All the material was taken from Reference 1. Theorem 4.5, Complementary Slackness Theorem, Example 4.4. READING ASSIGNMENT, A Geometric View, pg 153. Comments on the Dual Simplex Method, Section 4.5. Theorem 4.6 Farka's Lemma, Corollary 4.3, Theorem 4.7. READING ASSIGNMENT Applications of Farka's Lemma to Asset Pricing pg 167.

24. August 5th, 2019. Theorem 4.9, Alternative proof of Theorem 4.11, for general infinite dimensional Hilbert Spaces. Revisiting Farka's Lemma. READING ASSIGNMENT proof of Theorem 4.11, pg 170 and The Duality Theorem Revisited pg 173: material taken from Reference 1. . Opening Chapter 10 Integer Programming Formulations. The Job Assignment Problem, The 0-1 Knapsack Problem pg 5, 6: material taken from Reference 5.

25. August 8th, 2019. The 0-1 Knapsack Problem, The Set Covering Problem, The Traveling Salesman Problem, The Combinatorial Explosion, pags 6-8. Formulations of a Linear Integer Problem and Perfect Formulation of an LIP, Definition 1.2, Reference 5. From Reference 1.: Forcing Constraints, Example 10.2, Relations Between Variables, Disjunctive Constraints, Finite Range of Values pgs 453-454. READING ASSIGNMENT A sequencing Problem with Setup Times & Allocation of NSF Fellowships, pgs 457-461.

26. August 10th, 2019. SECOND TEST, you can download it HERE. The first part is individual, you can consult the textbook (Reference 1) and your class notes. For the computational part you can work in groups your papers are due August 13th at 12:00 M, the folder Second Test Files containing all the files can be accessed through this link.

27. August 13th, 2019. SECOND TEST COMPUTATIONAL PART DEADLINE EXTENDED UNTILL FRIDAY THE 16th, 23:59. Remember that your theoretical answers as well as your explanations of the decisions made have to be typed up in LaTeX. The course was finished at this point. Thanks to all the participants for their stamina during the process and the tests!!!

This is the list of references to be used in order of priority.

1. Introduction to Linear Optimization. Bertsimas, Tsitsiklis.

2. Linear Optimization: The simplex Workbook. Glenn Hurlbert. (Freely available for UNAL students.)

3. Combinatorial Optimization. Algorithms and Complexity. Papadimitriou C, Steiglitz K.

4. Introduction to Linear Algebra, 5th Edition. Gilbert Strang.

5. Integer Programming Laurence A Wolsey.