CS4234 - Optimisation Algorithms

Introduction

Overview (from Dr Seth Gilbert's version of S1 AY 2015/16 - 5 AYs ago): This course focuses on algorithms for solving optimization (American spelling) or optimisation (British spelling) problems, particularly focusing on combinatorial optimization. These types of problems are ubiquitous, with applications in a multitude of domains. They are used by companies to manage supply chains, retail chains to decide where and when to open new stores, and ports to manage incoming and outgoing cargo containers. In this course, we will cover a variety of powerful techniques for solving these types of problems.

Official description: This module covers common algorithmic techniques for solving optimisation problems, and introduces students to approaches for finding good-enough solutions to NP-hard problems. Topics covered include linear and integer programming, network flow algorithms, local search heuristics, approximation algorithms, and randomized algorithms. Through analysis and application of the techniques to a variety of canonical problems, students develop confidence to (i) appropriately model a given optimisation problem, (ii) apply appropriate algorithmic techniques to solve the problem, (iii) analyse the properties of the problem and candidate algorithms, such as time and space complexity, convergence, approximability, and optimality bound.

Note: This introductory message will not be prominent the next time you visit this URL again. This behavior is normal. You can view it again by scrolling to the top of this page.

Course Registration

The upperbound number of CS4234 students for Semester 1 (S1) AY20/21 is approximately about 15 less than the past 5 AYs, which is 60-15 = at most 45 students due to ZERO exchange student (S1 SEP is cancelled, both for incoming exchange students and outgoing NUS exchange students). CS4234 usually has about ~10 exchange students annually. Steven conservatively estimates that there will only be about ~26 students this time (running average in the past 4 AYs is ~33 students/year) - Steven will prepare at least two tutorial sessions, one F2F (for those who prefer that way and in NUS zone C) and one more online (for those who prefer that way, not in NUS zone C, or still stuck overseas). That estimate of ~26 students for lecture and ~13 per tutorial group (but not necessarily equal size) fall into 'small' class size. The latest COVID-19 advisory says classes ≤ 50 can go F2F so this is the current plan as of 23 July 2020..

The actual number of CS4234 students for Semester 1 (S1) AY20/21 is currently 61 students (as of 12 August 2020). As per latest COVID-19 advisory, I am instructed to go to e-Learning (for now)... We will also run 3 tutorial groups (1 F2F/zone C, 2 online/zone-free).

Useful information that has been used by current students to decide on whether they should register for CS4234 (see CS4234 in nusmods.com) in S1 AY20/21:

  1. It is Steven's fifth iteration. The first four iterations went relatively well and several known weaker spots will continually be improved. Steven did his PhD thesis around this topic more than ~16 years ago (2004) and teaching the first iteration four years ago (2016) has refreshed his own knowledge of this topic. Back in 2017, VisuAlgo started to have some NP-hard/complete visualization topics created by the 2017 TA of this module (Muhammad Rais). Hopefully the fifth iteration will run at least equal or even better than the first four iterations :).
  2. Teaching staffs:

    (Senior) Lecturer: Dr Steven Halim, the key man behind VisuAlgo that will be used with increasing importance in some of CS4234 lectures. Steven is working towards fully flipping almost every modules that he teaches... PS: His 'Dr' title was obtained after ~6 years working on (visualizations of local search algorithms on) NP-hard Combinatorial Optimization Problems (2004-2010)...

    Teaching Assistant (TA): Ammar Fathin Sabili, IOI Bronze 2013; IOI Problem Author 2018, already did CS4234 TA S1 AY19/20 with rating 4.3/5.0 (good) :).

    Machines, e.g., VisuAlgo and Kattis will continue be used to help Steven run this module...

    Rating
    (out of 5.0)
    (SoC avg ~4.1)    		 Aug-Nov 2020
    (n=??/??)
    ??%    		 Aug-Nov 2019
    (n=18/32)
    56% ▼    		 Aug-Nov 2018
    (n=19/26)
    73% ▲    		 Aug-Nov 2017
    (n=20/33)
    60% ▲    		 Aug-Nov 2016
    (n=23/40)
    58%
    Module feedback Target ≥ 4.2 4.2 ▼ (> avg) 4.3 ▼ 4.4 ▲ 4.00
    Module difficulty Target ≤ 4.1 4.2 == (> avg) 4.2 ▲ 4.1 ▼ 4.13
    Steven's teaching Target ≥ 4.3 4.7 ▲ (PB, > avg) 4.6 == 4.6 ▲ 4.53

Syllabus

For the fifth iteration of CS4234, Steven uses the following lesson plan (initially derived from Dr Seth Gilbert's version of S1 AY15/16 but has significantly branched out since then):

  • Part 1 (about 4 weeks): (Combinatorial) Optimization Problems:
    1. Some NP-hard (Combinatorial) Optimization Problems: Min-Vertex-Cover (2 variants, both are available @ VisuAlgo), Max-Independent-Set, Max-Clique, Min-Set-Cover, Steiner-Tree (3 variants, the General-Steiner-Tree variant is available @ VisuAlgo), Traveling-Salesman-Problem (4 variants, one is available @ VisuAlgo), and a few others (in tutorial)
    2. Current Approaches: Special Case(s), Small Instance/Parameterized Solution(s), Approximation Algorithm(s), and one more at Part 3
    3. Techniques Covered: (Clever) Brute Force/Complete Search, Dynamic Programming, Greedy Algorithm, Approximation Algorithm, Linear Programming, Integer Linear Programing (with relaxation)
  • Part 2 (about 4 weeks): Network Flows and Matching:
    1. Problem Definition and Basic Algorithm: The Ford Fulkerson's Algorithm (faster analysis)
    2. Analysis of various Augmenting Path heuristics for Ford Fulkerson's Algorithm, some have Max Flow Visualization @ VisuAlgo
    3. The Push-Relabel Algorithm
    4. Graph Matching Algorithms, especially the Unweighted Bipartite Matching Visualization @ VisuAlgo
    5. Harder Graph Matching applications/algorithms: Kuhn-Munkres (not yet in VisuAlgo) and Edmonds' Matching Algorithms (has VisuAlgo)
  • Part 3 (about 4 weeks): (Meta-)Heuristics/(Stochastic) Local Search:
    1. Techniques Covered: Gradient Descent/Hill Climbing, Simulated Annealing, Tabu Search, Iterated Local Search, etc
    2. A Trip to the Past: Discussing Steven's past PhD Thesis about Optimization Algorithms (2004-2010): SLS Design and Tuning Problem
  • Throughought this module:
    1. Lots of Proofs :O (but we will skip some complicated one-time proofs in class if they become too dry but the details are in the lecture notes/tutorial modal answers)
    2. Implementation of (some of) these advanced optimization algorithms (via help of Online Judge) and their empirical analysis (especially for Part 3)

Course Registration Additional FAQ

If you have any important questions regarding this module, email stevenhalim at gmail dot com. Relevant answers will be posted here to reach wider audiences.

Q: Will this module be graded using Bell curve?
A: Historically, with average of ~33 students in the past 4 AYs, Steven usually do not have to follow Bell Curve system for CS4234... and this S1 AY20/21 class size is expected to be slightly smaller because there is no exchange student... BELL CURVE WILL BE USED as 53 > 40...
Q: Will this module flocked by students who have (very) good CS3230 grades?
A: Experience from past AYs tell Steven that the answer is not 100% true, but indeed many students from the earlier iterations have reasonably strong interest in algorithm (thus reasonably good CS3230 grades and also good grades on previous related algorithm modules).
Q: Will this module flocked by students who have taken CS3233?
A: In recent AYs, there is an increasing trend that a fraction of Steven's past CS3233 students are now taking CS4234 too (the reverse is actually rarer as CS4234 is coded as a level 4 module and CS3233 is coded as a level 3 module).
Q: Is this module suitable for (advanced) exchange students?
A: In recent AYs, Steven also recognizes the growing number of exchange students taking this module. But since SEP S1 Y20/21 has been cancelled, there will be 0 exchange student this time and that will easily set class average from ~33 to maybe 26+ only, expecting a very small class...
Q: How different will this year's (AY20/21) version be compared to last four years (AY19/20, AY18/19, AY17/18, AY16/17) versions?
A: The fifth iteration will continue to be a local improvement on the relatively successful first four iterations. Steven will only do these minor local changes: most likely some form of recording (to facilitate potential online classes due to COVID-19), a few instance of live coding demonstration, moving PS2 tasks from Mooshak to Kattis format, (slightly) better proof presentation in lectures and tutorials, asking more proving questions in tests, (slightly) less competitive than the first four iterations, (more basic stuffs delegated to VisuAlgo e-Lecture/flipped classroom), continue refining the more interesting Graph Matching topics: Kuhn-Munkres and Edmonds' Matching Algorithm.
Q: Will there be some form of coding in this course?
A: The lecturer is a competitive programmer, has written a book (now two separate books) about it, and manages various programming competitions in SoC/Singapore/Worldwide :O. So yes, there will always be implementation side of the various optimization algorithms that we discuss in class. You will implement real algorithms to attack real NP-hard optimization problems throughout this module. See CPbook Methods to Solve, CS4234 related stuffs. Warning: Some of these (NP-)hard optimization problems discussed in class are time limit-critical... so students who can only code in Python will be at strong disadvantage at some programming exercises. Java coder is still somewhat affected (but will 99% able to also solve the programming exercises with the same algorithm or different algorithm but similar time complexity). C++ coder is preferred.
Q: Do I have to buy any textbook for this course?
A: My Competitive Programming book: CP4, book two (actually for CS3233), can be a good book for about two-thirds of the module topics (especially the implementation side) of CS4234 (Network Flow, Graph Matching (including some of the rare ones), NP-hard/complete problems). Introduction to Algorithms (by CLRS, the typical textbook used in CS3230) and Algorithm Design (by Kleinberg and Tardos) are also recommended.

Note: This course registration section will not be prominent from Week 02 onwards (after the first lecture). This behavior is normal. You can view it again by scrolling to the top of this page.

News

Date News

Lesson Plan

Week Tutorial
Mon, 11am-12pm/T1 (COM1-VCRM, F2F)
Mon, 2-3pm/T2 (Zoom, online)
Mon, 5-6pm/T3 (Zoom, online)
Open ended consultation slot TBC		 Lecture
Thu 12-2pm
I3-Aud (big enough for social distancing, will be webcasted)strike>
e-Learning via Zoom :O...		 Assignment
Cells with course material that have not been updated are highlighted with pink color, past classes more than one week ago are hidden so that we can focus on the current and future classes, but you can restore them by clicking 'Show Past' button above, future classes are not highlighted
00,
Bef
10
Aug 		Not Started Not started
But please revise your CS1020+CS2010 (or CS2020/CS2040) and CS3230
Use this set for your revision (CS1010+CS2040+CS3230 stuffs)
PS: If you have taken CS3233 before, revise Max Flow, Matching, and NP-hard/complete that we have discussed in CS3233 before 		Not Started
01,
10-14
Aug 		Not started National Day is on Sun, 09 Aug 2020
The following Mon, 10 Aug 2020 is a Public Holiday
CS4234 first lecture is not affected
00.Introduction.pptx (2019)
01.VertexCover.pptx (2019), 01.VertexCover.pdf (2017)
Extra Reference: MVC @ VisuAlgo (the unweighted version)
Understanding Unsolvable Problem
(Re)-Introduction to the Min-Vertex-Cover problem (CS3230 review) and the 3C2 idea
 		PS1-(NP-)hard Optimization 1
Out on ???, ?? Aug 2020, ??.00?m
nus.kattis will help Steven checks your code
PS1 runs until end of Week 03 so you have time for self-study
And there is time to discuss PS1 during Week03 Lecture/Tutorial

Use all these information to decide whether CS4234 is for you
Or drop it before end of Week 02
02,
17-21
Aug 		Not Started 02.LPIntro.pptx (2019), 02.LPIntro.pdf (2016)
Extra Reference: MVC @ VisuAlgo (the weighted version)
Extra Material: 02.ExcelSample.xlsx, lp_solve tutorial,
Simplex code in C++ or Java
Introduction to (Integer) Linear Programming + Relaxation
The Min-Weight-Vertex-Cover problem
 		PS1, continued

Do not forget to decide whether CS4234 with all those (NP)-hard problems
is for you (or not) by end of this Week 02...
03,
24-28
Aug 		T01.pdf, T01-ans.pdf (see LumiNUS)
The Intro COP:
Min-(Weight)-Vertex-Cover
LP, Max-Clique,
(optional) PS1 discussion,
pseudo-polynomial DP
 		03a.SetCover.pptx (2019), 03a.SetCover.pdf (2016)
Another Combinatorial Optimization Problem (COP): Min-Set-Cover

03b.SteinerTree.pptx (2019), 03b.SteinerTree.pdf (2016)
Yet another COP: Steiner-Tree (3 variants)
Extra Reference: Steiner Tree @ VisuAlgo (the general/graph version)
 		PS1 due
on Sat, 29 Aug 2020, 07.59am (5%)

PS1-(NP-)hard Optimization 2
Out on Sat, 29 Aug 2020, 08.00am
04,
31 Aug-
04 Sep 		T02.pdf, T02-ans.pdf (see LumiNUS)
PS1 Debrief
3 More COPs:
Min-Set-Cover
Steiner-Tree
Min-(Weight)-Feedback-Edge-Set
 		04.TSP.pptx (2016), 04.TSP.pdf (2016)
Going deeper on this classic Travelling-Salesman-Problem
Extra Reference: TSP @ VisuAlgo
Extra Material: Someone made a movie out of this: Trailer, Movie website
 		PS2, continued
05,
07-11
Sep 		T03.pdf, T03-ans.pdf (see LumiNUS)
2++ More COPs:
Travelling-Salesman-Problem
Max-Independent-Set
 		05a.MaxFlow.pptx (2019) + 05b.FFAnalysis.pptx (2016)
Introduction to Max-Flow Problem (flipped classrom)
Ford-Fulkerson Algorithm (quick run through)
Max-Flow/Min-Cut Theorem (in details)
Analyzing the performance of Ford-Fulkerson (quick analysis)
Other Augmenting Path Heuristics: Fattest-Path, Capacity-Scaling (skipped),
'Tighter' FF analysis: Edmonds Karp's Algorithm (in details)
Dinic's algorithm (quick analysis)
Max-Flow Visualization @ VisuAlgo 		PS2 due
on Sat, 12 Sep 2020, 07.59am (5%)

PS3-Mini Researcher,
Out on Sat, 12 Sep 2020, 08.00am
PS3 is a written PS
The task requirements and associated files
are uploaded to LumiNUS Files
Online IOI 2020, 13-19 Sep 2020
Steven is super busy with the rescheduled online IOI 2020
Hence Week 06 lectures will be pre-recorded and Tut+PS2 queries all handled by TA
06,
14-18
Sep 		T04.pdf, T04-ans.pdf (see LumiNUS)
Back to a P optimization problems: Max-Flow
Max-Cardinality-Bipartite-Matching
Max-Independent(/Edge-Disjoint)-Path
Min-Cut
Alternative Ford Fulkerson's analysis
 		[RECORDED E-LECTURE] 06.PushRelabel.pptx (2016)
Introducing the Push-Relabel Algorithm
Sample (manual) execution
(no VisuAlgo page yet involving Push-Relabel)
Analysis of Basic Push-Relabel Algorithm
 		PS3, continued
Recess Week, 19-27 Sep 2020
We can take a break this week :)
07,
28 Sep-
02 Oct 		T05.pdf, T05-ans.pdf (see LumiNUS)
Assignment-Problem
Discussion about O(n3) Push-Relabel algorithm
 		07.Matching.pdf (2019)
Introduction to (Weighted) Max-Cardinality-(Bipartite)-Matching Problem
Week 07 focus: MCBM and its applications
Max-Flow, Augmenting Path Algorithm++, Hopcroft Karp's/Dinic's Algorithm
Graph Matching Visualization @ VisuAlgo (for Unweighted MCBM)
PS3 due
on Sat, 03 Oct 2020, 07.59am (5%)

PS4 - Flows+Matchings
Out on Sat, 03 Oct 2020, 08.00am
08,
05-09
Oct 		T06
Monday groups: Midterm test preparation
Thursday group: Midterm test debrief
Ammar has the modal answers of past 3 papers.
 		Midterm Test (25%)
Material: Week01-06, up to Max Flow (Push Relabel)
Including stuffs from PS1-3 (PS3 task 3 style question appears)
(solving some PS4 problems early is good to have but not crucial;
only ~[15..30]% questions on Max-Flow)
Open book (no restriction on this)
Only one constraint: No electronic device (except normal calculator)
PS: If this test cannot be done onsite,
Steven will update this section with the stricter online test version

Past papers:
Midterm test paper (S1 AY 2016/17),
Midterm test paper (S1 AY 2017/18),
Midterm test paper (S1 AY 2018/19),
Midterm test paper (S1 AY 2019/20).
TBC: Sat, 10 Oct 2020, NUS ICPC Team Selection Contest
Some problems are relevant to CS4234,
e.g., those that say 'maximize that' or 'minimize this' 		PS4, continued
09,
12-16
Oct 		T07.pdf, T07-ans.pdf (see LumiNUS)
One more Push-Relabel question
Discussion about Graph Matching problems/algorithms
Application of Matching/Max-Flow on two NP-hard COPs
Two other applications of (Weighted) (Bipartite) Matching
Monday groups only: Optional Midterm test debrief
 		08.Matching2.pdf (2019)
Week 09 focus: Weighted MCBM (MCMF or Hungarian),
Unweighted MCM (Edmonds's Matching),
Weighted MCM (small graph),
Wrap-ups of Graph Matching Topic
Hungarian Method visualization @ TUM
Graph Matching Visualization @ VisuAlgo (for Unweighted MCM)
 		PS4, continued
10,
19-23
Oct 		T08.pdf, T08-ans.pdf (see LumiNUS)
More graph matching questions
Another Optimization Problem involving matching
Unweighted MCM,
Weighted MCBM
 		09.StochasticLocalSearch.pdf (2016)
Introduction to Stochastic Local Search (SLS)
Paradigm change, SLS Characteristics,
No proof, just experiments... 		PS4 due
on Thu, 22 Oct 2020, 07.59am (5%)

Mini-Project - Local Search
Out on Thu, 22 Oct 2020, 12 noon
Proper launch during Lecture 10
11,
26-30
Oct 		T09.pdf, T09-ans.pdf (see LumiNUS)
Discussion about Stochastic Local Search
Using Mini Project topic as the context
 		10.Meta-heuristics.pdf (2016)
Discussions of a few, more-sophisticated SLS algorithms
Simulated Annealing, Tabu Search, Iterated Local Search, Evolutionary Algorithms, etc...
Highlight on the need of tuning certain parameters of those SLS algorithms...
 		Mini-Project, continued
12,
02-06
Nov 		T10.pdf, T10-ans.pdf (see LumiNUS)
SLS Review 1
Discussion about SLS DTP
Past Paper discussion 1
Optional: Mini Project progress discussion

"Active in Class" achievement will be finalized this week
Tutorial Participation Marks given (5%) 		11.SLS-DTP.pdf (2016)
SLS Design and Tuning Problem (DTP)
Designing SLS algorithm; Doing (Parameter) Tuning;
Fitness Landscape and Search Trajectory Analysis
Example on another NP-hard COP: Quadratic-Assignment-Problem
qap_a-ro-ts-i.avi, qap_a-ro-ts-a.avi, qap_b-ro-ts-i.avi, qap_b-ro-ts-b.avi, QAP_FL_Demo.exe

NUS Online Teaching Feedback System opens this Friday
 Mini-Project, continued
13,
09-13
Nov 		T11 is simply a past paper review slot
Past Paper discussion 2
Final class photo
Optional: Mini Project progress discussion
 		First ~1+ hour: Mini Project Presentations
By 32/4 = 8 project groups
At most 8x(3m/TSP+3m/MWVC+1m/short QnA+2m/buffer) = 72 minutes

Closed by:
Module review
Reminder about Teaching Feedback
Invitation to do PhD in algorithm... :)
Steven's PhD Thesis: 2004-2010 is downloadable from NUS ScholarBank
Final assessment preview
Official class photo
Deepavali is on Sat, 14 Nov 2020
No CS4234 class is affected
 		Mini-Project due
on Thu, 12 Nov 2020, 11.59am (15%)
Before last lecture,
you will present your work during the first hour
(up to 70 minutes) of last lecture
Study Week
Final Assessment Consultations (per request)

NUS Online Teaching Feedback System closes on Friday of Study Week
Final Assessment, ???, ?? ??? 2020 (?M, ?-??m SGT),
Venue: TBC (35%)
We aim to do this paper face to face but may have to move to online format depending on COVID-19 situation by then...
Past Papers:
Final paper (S1 AY 2016/17),
Final paper (S1 AY 2017/18),
Final paper (S1 AY 2018/19),
Final paper (S1 AY 2019/20, without the MCQs).

Class Roster

Steven uses a small-scale gamification system in his version of CS4234 for extra study motivation.
The list of possible achievements are as follows: (achievements highlighted with red color/green color are already completed in the past/being given, respectively)

  1. I Say Hi: Given to first 7 students who reply Steven's welcome email (sent on Thu, 06 August 2020, 2.59pm); Any early feedback will always help Steven in refining the preparation of the next iteration of this module, now 'forced' to be online (for lecture). Steven still insists to have at least one tutorial F2F for zone C students
  2. In Kattis: Given to students who are already registered in nus.kattis (closed after tutorial 01)
  3. In FB: Given to students who are already in CS4234 FB group (closed after tutorial 01)
  4. Kiasu (#): Given to the first 7 students who solve all tasks of PS1-(NP-)hard Optimization 1
  5. Approximation Master (#): Given to the first 7 students who solve all tasks of PS2-(NP-)hard Optimization 2
  6. Mini Researcher (#): Given to top 6 students who have 100 points in PS3 (written)
  7. Flows Like Water (#): Given to the first 7 students who solve all (different) tasks of PS4-Flows
  8. Test Master (#): Given to the top 4 students who have Midterm Test scores ≥ 80 points (after moderation)
  9. Active in Class: Given to the top 3 students per tutorial group who participated the most in our first 9+ tutorial classes (Given on Week 12, these students will get full 5% tutorial participation points, the rest will fight for 4, 3, 2, 1% tutorial participation points)
  10. Future Algorithm Researcher: Given to top 2 project groups who perform well in their mini project about SLS experiments on two (NP-)hard COPs
  11. Nowhere to Hide (Reason): Given to students who already remembered by Steven (stopped by last lecture); These students can choose to hide their matric cards during CS4234 official assessments and Steven will allow them to do so
  12. Kattis Mini Apprentice (Kattis profile link): Given to students who manage to get 300.0 or more Kattis points at open.kattis during the execution of CS4234 in S1 AY20/21 (closed by last lecture); doing Week 00 Warm-up+PS1+2+4+Mini Project will only give you about ~100.0 Kattis points... so you must have done a lot more extra homework than necessary; PS: This is my account and this CS4234-specific page of Methods to Solve can help you get this achievement)
No Tut Student Name Achievements