Martin Gairing
University of Liverpool
Univ Liv » Comp Sci » Ec Co » Martin Gairing » COMP557
COMP331 / COMP557


Martin Gairing
Ashton Building
Room 3.03
gairing [at]

If you wish to see me, please talk to me after class or send an email to make an appointment.

Meeting Times

Lecture Times and Locations:

  • Tuesday 9:00 - 10:00: Ashton Lecture Theatre

  • Wednesday 12:00 - 13:00: Ashton Lecture Theatre

  • Friday 13:00 - 14:00: Ashton Lecture Theatre



Course Outline and Lecture Notes

Tentative Outline

  • introduction
  • linear programming and the simplex algorithm
  • geometric interpretation of the simplex algorithm
  • LP dualty
  • optimisation in practise

Lecture Notes

Exercise Sheets

Lab on 8 Oct:
Sheet Exercises Handout Turnin/Discussion Notes
1 (pdf) 1 5.10.2018
2 (pdf) 2-4 8.10.2018 18.10.2018 Ex.4 will be marked.
3 (pdf) 5-6 12.10.2018
4 (pdf) 7 19.10.2018
5 (pdf) 8-10 25.10.2018
6 (pdf) 11 2.11.2018
7 (pdf) 12-14 9.11.2018
8 (pdf) 15-16 16.11.2018
9 (pdf) 17 23.11.2018

Final continuous assessment task

This task will contribute 10% to your final mark. You will be working on some topic related to the material covered in the lectures. The topic you are assigned to is determined by the programme you are studying. You are allowed and encurraged to work and submit in groups of up to 3 students. Each group has to write a 2-page summary on the topic.

  • Dantzig-Wolfe Decomposition
    The Dantzig-Wolfe Decomposition is a method designed for large scale linear programming problems having a certain structure. It is covered in Chapter 6 of Bertsimas, Tsitsiklis.
    • MSc Big Data and HPC (CMBD, CMBI)
  • Sensitivity Analysis This topic is covered in Chapter 5 of Bertsimas, Tsitsiklis. Your summary should cover the most important aspects.
    • All COMP331 students (G401, G403, G40A, GN34, N300)
  • Network-Simplex Algorithm This algorithm is a simplification of the simplex method to problems having a certain structure. A textbook coverage of the network-simplex algorithm can e.g. be found in [Chvatal (1983). Linear Programming. Chapter 19.] You should explain the main ideas of this algorithm.
    • MSc Advanced Computer Science (CSAD,CSAI)
  • Lemke-Howson Algorithm This algorithm was develloped for finding a Nash equilibrium in a 2-player bimatrix game. A good covarage of the algorithm can be found in Chapter 3 of [Algorithmic Game Theory, Cambridge University Press, 2007. Nisan, Roughgarden, Tardos, Vazirani, eds.]. You should explain the algorithm and how it relates to the simplex algorithm.
    • Advanced CS with Internet Economics (CSCI, CSCN)

Pointers to the above referenced literature can be found here.

Each group will have to submit a 2-page summary of the topic in PDF format.
Deadline for the 2-page report is on 28 November 2018 30 November 2018, 5pm.
A marking guidline for this assignment can be found here.

Submission Instructions: Please submit your 2-page summary using the link that corresponds to your module code by 28 November 2018, 5pm. No late submissions accepted. Please make sure to include the names of all group members in your pdf file.

Other Resources

Stuff from the board: (will be updated after every lecture)

Text Books

The main textbook for the course is:

Introduction to Linear Optimization, Athena, 1997.
D. Bertsimas, J. N. Tsitsiklis


  • Coursework: 25 %
    • 18/10/18 : Gurobi programming assignment, 5%
    • 15/11/18 : Classtest, 10%
    • 28/11/18 30/11/18: Summary to some related topic, 10%
  • Final Exam: 75 %
    The exam will be 2.5 hours long. Details will follow.

Old Exam Papers

Old exam papers for CS modules can be found here: Here are the exam papers of the last years:

last modified: 07 December 2018 | yummy built with TT | Layout by Christian Kreibich (cc)