Instructor:
Martin Gairing
Ashton Building
Room 3.03
gairing [at] liverpool.ac.uk
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
Tutorials:
tba
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) 
24 
8.10.2018 
18.10.2018 
Ex.4 will be marked. 
3 (pdf) 
56 
12.10.2018 


4 (pdf) 
7 
19.10.2018 


5 (pdf) 
810 
25.10.2018 


6 (pdf) 
11 
2.11.2018 


7 (pdf) 
1214 
9.11.2018 


8 (pdf) 
1516 
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 2page summary on the topic.
Topics:

DanzigWolfe Decomposition
The DantzigWolfe Decomposition is a method designed for large scale linear programming problems
having a certain structure. It is covered in Chapter 6 of Bertsimas, Tsitsiklis.
Students:
 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.
Students:
 All COMP331 students (G401, G403, G40A, GN34, N300)

NetworkSimplex Algorithm
This algorithm is a simplification of the simplex method to problems having a certain structure.
A textbook coverage of the networksimplex algorithm can e.g. be found in [Chvatal (1983). Linear Programming. Chapter 19.]
You should explain the main ideas of this algorithm.
Students:
 MSc Advanced Computer Science (CSAD,CSAI)

LemkeHowson Algorithm
This algorithm was develloped for finding a Nash equilibrium in a 2player 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.
Students:
 Advanced CS with Internet Economics (CSCI, CSCN)
Pointers to the above referenced literature can be found here.
Each group will have to submit a 2page summary of the topic in PDF format.
Deadline for the 2page report is on 28 November 2018, 5pm.
A marking guidline for this assignment can be found here.
Submission Instructions:
Please submit your 2page 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
Assessment
 Coursework: 25 %
 18/10/18 : Gurobi programming assignment, 5%
 15/11/18 : Classtest, 10%
 28/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:
