DM554 – Linear and Integer Programming

Syllabus

Linear Algebra Part:

  • Matrices and vectors
    • Matrix algebra
    • Geometric insight, lines and hyperplanes
  • Systems of Linear Equations
    • Row echelon form, Gaussian elimination
  • Matrix inversion and determinants
  • Rank, range and linear equations
  • Vector spaces
    • Definition
    • Subspaces
    • Linear independence
    • Basis and dimension
    • Change of basis
  • Linear Transformations
    • Matrix representation
  • Orthogonality
    • Scalar product
    • Orthogonal subspaces
    • Inner products
  • Diagonalization
    • Eigenvalues and Eigenvectors
    • Diagonalization of square matrix
    • Quadratic forms
    • Positive definite forms

Linear Programming Part:

  • System of Linear Inequalities
    • Fourier Motzkin
  • Linear programming
    • Resource allocation in factory planning. Diet problem.
    • Linear programming problems and geometrical interpretation. History
    • Notation
    • Fundamental theorem
  • Simplex Method and Exception Handling
    • tableaux
    • exception handling and degeneracies
    • Pivot rules
    • Initialization
  • Duality Theory
    • bounding and multipliers approach
    • Weak/strong duality theorems and complementary slackness theorem
    • Duality by Lagrangian multipliers
    • Dual Simplex.
    • Economic interpretation
  • Sensitivity Analysis
    • Geometric interpretation
    • Sensitivity analysis, examples.
    • Farkas Lemma and infeasibility certificates
  • Revised Simplex Method
  • Integer Programming
    • Modeling
    • Covering, Knapsack, Assignments, Matchings, Graph Problems
    • Disjunction constraints, Uncapacitated facility location problem, TSP
    • Relaxations, Primal and dual bounds,
    • Properties of easy problems.
  • Well Solved Problems, Network Flows
    • Convex hull description, Total unimodular matrices,
    • Network flows, Maximum flow, Min cost flow, models, algorithms and examples
    • Duality of Network Flow problems and Network Simplex
  • ILP in Excel
  • Cutting Planes - Branch and Bound
    • Valid Inequalities, Formulations, strength, inequalities.
    • Chvatal Gomory cuts
    • Cutting plane algorithm. Gomory's fractional cutting plane algorithm, example
    • Branch and Bound, example
  • Preprocessing
    • Set covering preprocessing
    • Modelling tricks in IP, nonlinear programs, piecewise functions
  • Interior Point Method

Date: 2015-02-02T09:06+0100

Author: marco

Org version 7.9.3f with Emacs version 24

Validate XHTML 1.0