COMP 3753: Computational Aspects of Linear Programming

Those who wish to have an introduction to linear optimization problems that arise in many areas such as operations research.

Prerequisites:  COMP 1001 or the former COMP 2710, and Mathematics 2050

Availability: ⚠ This course is not planned to be offered in the near future.

Course Objectives

To analyze the Linear Programming (linear optimization) Problem, to investigate the recent developments in the theory necessary to solve this problem, to design efficient algorithms for its solution and to analyze the complexity of these algorithms and their numerical efficiency.

Representative Workload
  • Assignments 50%
  • In-class Exam 20%
  • Final Exam 30%

Programming assignments emphasize the numerical dangers that may appear because of the finite precision of computers. Some of the programming will use MATLAB.

Representative Course Outline
  • Brief review of necessary linear algebra
  • Introduction to the Linear Programming Problem (LPP)
  • The simplex algorithm
  • Sparse matrix techniques for the LPP problem
  • Duality and postoptimality analysis
  • Extensions to the simplex algorithm
  • A brief introduction to interior algorithms for the LPP

Page last updated May 24th 2021