DM545 – Linear and Integer Programming

Syllabus

  • 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:05+0100

Author: marco

Org version 7.9.3f with Emacs version 24

Validate XHTML 1.0