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

Instructor:

Martin Gairing
Ashton Building
Room 3.03
m.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 3 Oct:
Sheet Exercises Handout Turnin/Discussion Notes
1 (pdf) 1 3.10.2017
2 (pdf) 2-4 10.10.2017 20.10.2017 Ex.4 will be marked.
3 (pdf) 5-6 13.10.2017
4 (pdf) 7-9 23.10.2017
5 (pdf) 10-12 3.11.2017
6 (pdf) 13-15 10.11.2017
7 (pdf) 16-17 17.11.2017
8 (pdf) 18 24.11.2017


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 up to 4 students. Each group has to write a 2-page summary on the topic.
Topics:

  • Danzig-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.
    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)
  • 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.
    Students:
    • MSc Advanced Computer Science (CSAD)
  • 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.
    Students:
    • Advanced CS with Internet Economics (CSCI, CSCN)

Pointers to the above referenced literature can be found here.

Each group (of up to 3 students 4 students) will have to submit a 2-page summary of the topic in PDF format.
Deadline for the 2-page report is on 29 November 2017, 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 29 November 2017, 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 %
    • 20/10/17 : Gurobi programming assignment, 5%
    • 15/11/17 : Classtest, 10%
    • 29/11/17 : 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: 02 November 2017 | yummy built with TT | Layout by Christian Kreibich (cc)
)