Academic Year 2022 - 2023
Semester 2

NUSMods Description

The objective of this course is to work on optimization problems which can be formulated as linear and network optimization problems. We formulate linear programming (LP) problems and solve them by the simplex method (algorithm). We also look at the geometrical aspect and develop the mathematical theory of the simplex method. We further study problems which may be formulated using graphs and networks. These optimization problems can be solved by using linear or integer programming approaches. However, due to its graphical structure, it is easier to handle these problems by using network algorithmic approaches. Applications of LP and network optimization will be demonstrated. This course should help the student in developing confidence in solving many similar problems in daily life that require much computing. Major topics: Introduction to LP: solving 2-variable LP via graphical methods. Geometry of LP: polyhedron, extreme points, existence of optimal solution at extreme point. Development of simplex method: basic solution, reduced costs and optimality condition, iterative steps in a simplex method, 2-phase method and Big-M method. Duality: dual LP, duality theory, dual simplex method. Sensitivity Analysis. Network optimization problems: minimal spanning tree problems, shortest path problems, maximal flow problems, minimum cost flow problems, salesman problems and postman problems.

Review

This module is my first Maths 3K module and was taught by Professor Zhao Gongyun. He is an expert in optimisation problems and quite a good explainer. There are lectures on Friday at the most ungodly time ever (7 pm - 10 pm). I attended the first 2 lectures and the day where there is a midterm. I just use my Saturday morning to watch the lecture recording.

I think this module is quite challenging but very fulfilling. I learnt about Linear Programs in CS3230 Design and Analysis of Algorithms but it was not taught in depth at all. There are times when the notation was a bit too much and studying the notes became very hard. However, over time, I got the hang of the notation and was able to explain a lot of the harder concepts. I was also able to relate to CS-related topics. This module is thus a very good module for CS students to reinforce what you learnt but in a more rigorous mathematical setting.

I think I have a very good tutor as well. Usually, tutors from the Math department are so dead but this one is the best so far. He is very articulate and I understood his teachings very much. He was able to answer some questions of mine quite well and even gave examples and proofs too.

In terms of assessment, the midterms were a bit too easy till the average is 49/60. I scored 53/60. Finals was quite trash for me. I wanted an A for this module and I actually was pretty confident. The hard part about the exams is that you essentially become a human calculator. Imagine doing 6 steps of the simplex algorithm only to realise you messed up in the middle – you essentially wasted the past 15mins of the exam. I did not do 1 question because I brain-farted. It was a simple execution of network simplex. Meanwhile for proof questions (my favourite), I zoomed through them because I enjoyed doing proofs for this module. I know my stuff, but the execution (especially when it comes to handwriting steps of an algorithm) is pretty bad. Got an A- in the end.

Overall, a fulfilling module. This is the module which I gained the most from this semester.