INF270: Linear Programming

This repository contains exercises and lecture notes for the course INF270.

Topics

Lecture 1 (link)

• General def. of LP

Lecture 2 (link)

• LP examples
• Transformation into standard form

Lecture 3 (link)

• Transformation into standard form (continued)
• The Simplex method (graphical approach)
• Unbounded LP

Lecture 4 (link)

• The Simplex method (step-by-step)

Lecture 5 (link)

• The Simplex method (continued)
• Auxiliary problem (where we don't have a feasible basis)

Lecture 6 (link)

• Degeneracy
• Unbounded (no solution)
• Cycling
• Lexicographic SM (to prevent cycling)

Lecture 7 (link)

• Lexicographic SM (continued)
• Bland's rule
• Geometry of LP

Lecture 8 (link)

• Degeneracy (continued)
• Efficiency of the Simplex method
• Klee-Minty
• Largest coefficient rule
• Computational complexity

Lecture 9 (link)

• Duality

Lecture 10 (link)

• Duality (continued)
• (P) negative transposed becomes (D)
• Complementary slackness condition (CSC)
• Complementary slackness theorem

Lecture 11 (link)

• Duality (continued)
• Dual Simplex method
• When both (P) and (D) are infeasible
• Dual-based phase I algorithm

Lecture 12 (link)

• (P)/(D) example (resource allocation problem)
• Strong duality theorem ("Lagrangian duality")
• The Simplex method in matrix notation

Lecture 13 (link)

• The Simplex method in matrix notation (continued)
• Complete example
• Dual problem in matrix form

Lecture 14 (link)

• The Simplex method in matrix notation (continued)
• Concrete example

Lecture 15 (link)

• The Simplex method in matrix notation (continued)
• Sensitivity analysis
• Concrete example

Lecture 16 (link)

• Sensitivity analysis (continued)
• The homotopy analysis method

Lecture 18 (link)

• LU-factorization
• Minimum degree ordering heuristic
• Complete example

Lecture 19 (link)

• Network flow problem
• Spanning trees and bases

Lecture 20 (link)

• Network flow problem (continued)
• Basis matrix theorem
• Dual solution of a network flow problem

Lecture 21 (link)

• Network flow problem (continued)
• Complete example
• SM for network flow problems
• Pivot step in the network flow SM

Lecture 22 (link)

• Dual network Simplex method
• Integrality theorem
• Interior point methods

Lecture 23 (link)

• Interior point methods (continued)
• Barrier function
• Non-linear programming (NLP)
• Kanish-Kuhn-Tucker system (KKT)
• Lagrange multiplier

Notes

The Duality Theorem

This will be important for the exam.