CS4234 - Optimisation Algorithms

Introduction

Overview (from Dr Seth Gilbert's version of S1 AY 2015/16 - 3 years 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 expected number of CS4234 students for Semester 1 (S1) AY18/19 is actually slightly larger than the past 3 AYs, which is 60 students. This is the initial number that Steven is working with when preparing this module albeit Steven has a feeling it will hover around 40+ after round 3B based on the enrollment data in the earlier rounds.

Useful information that has been used by current students to decide on whether they should register for CS4234 (see CS4234 in nusmods.com, no review though) in S1 AY18/19:

  1. It is Steven's third iteration. The two iterations went relatively well and several known weaker spots from the first two iterations will be improved in the third iteration. Steven did his PhD thesis around this topic more than ~14 years ago (2004) and teaching the first iteration two years ago (2016) has refreshed his own knowledge of this topic. By 2017, VisuAlgo started to have some NP-hard/complete visualization topics created by the 2017 TA of this module (Muhammad Rais). Hopefully the third iteration will run at least equal or even better than the first two 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): Gan Wei Liang, IOI International Scientific Committee member 2018-2021, Champion of ICPC Manila Regional 2017, CS4234 alumni (S1 AY17/18, A+), Student Tutor Honour List AY16/17.
    Lab TA (Grader): Yohanes Yudhi Adhikusuma, PhD Candidate, NUS SoC, CS4234 alumni (S1 AY16/17, A-).
    Machines, e.g. Mooshak, VisuAlgo, and Kattis will continue be used to help Steven run this module...

    Rating
    (out of 5.0)
    (SoC avg ~4.1)
    Aug-Nov 2018
    (n=??/33)
    70%+
    Aug-Nov 2017
    (n=20/33)
    60%
    Aug-Nov 2016
    (n=23/40)
    58%
    Module feedback Target: 4.3+ (maintain) 4.4 (above avg) 4.00
    Module difficulty Target: 4.1- (maintain) 4.1 (above avg :O) 4.13
    Steven's teaching Target: 4.4+ (let's see) 4.6 (above avg) 4.53

Syllabus

For the third 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-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
    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 3(+1 virtual) weeks): Network Flows and Matching:
    1. Problem Definition and Basic Algorithm: The Ford Fulkerson's Algorithm [will likely be turned into a flipped classroom]
    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 Bipartite and Non-Bipartite Unweighted Matching Visualization @ VisuAlgo
    5. NEW: More interesting Graph Matching applications/algorithms
  • 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)
    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: Depending on whether the final class size is ≥ 40 or < 40.
Q: Will this module flocked by students who have (very) good CS3230 grades?
A: From past 2 AYs, the answer is not 100% true, but indeed many students from the first two 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 many 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 take note that the pace of classes in NUS (Asian University) may be much faster than the pace in your home University...
Q: How different will this year's (AY18/19) version be compared to last two years (AY17/18 and AY16/17) versions?
A: The third iteration will continue to be a local improvement on the relatively successful first two iterations. He will only do these minor local changes: (slightly) less coding actually live demo coding, (slightly) better proof presentation, will ask more proving questions in tests, (slightly) less competitive than the first two iterations, (more basic stuffs delegated to VisuAlgo e-Lecture/flipped classroom), add new/harder/more interesting Graph Matching topics.
Q: Will there be some form of coding in this course?
A: The lecturer is a competitive programmer, has written a book 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.
Q: Do I have to buy any textbook for this course?
A: My Competitive Programming book, the CP3.18a edition (actually for CS3233) can be a good book for a small subset of the topics (especially the implementation side). But in CS4234, we will also discuss NP-hard problems that do not have efficient solutions (already covered a bit in CP3.18a edition and will continue to be expanded a bit more by CP4). Introduction to Algorithms (by CLRS, the typical textbook used in CS3230) and Algorithm Design (by Kleinberg and Tardos) are also recommended. Steven will also try to continue expanding Seth's initial LaTeX-style lecture summary that was already available for the Part 1 of the class but not yet available for Part 2-3 of the class.

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

After exam, Bay Wei Heng, Muhammad Irham R B Z, Ng Yi Chong Raynold (students) will also going to compete in ICPC Asia Yangon 2018.

Lastly, on 13 December 2018, many CS4234 staffs/students will be involved in ICPC Asia Singapore 2018.

Week Tutorial
Mon, 10-11 (3), 11-12 (2), or 17-18 (1)
Lecture
Wed 12-2pm, COM1-0204 (no webcast facility here)
Assignment

Cells with course material that are not ready yet are highlighted with light pink color, past classes are highlighted with khaki color, current week is highlighted with light green color, future classes are not highlighted
PS: Public holiday on Wed, 9 Aug 18 (Singapore National Day)
but CS4234 first lecture is not affected
00,
Bef
13
Aug
Not Started Not started
But please revise your CS1020+CS2010 (or CS2020/CS2040) and CS3230
PS: If you have taken CS3233 before, revise NP-hard/complete, Max Flow, and Matching that we have discussed in CS3233 before
Not Started
01,
13-17
Aug
Not started 00.Introduction.pptx (2018 version)
01.VertexCover.pptx, 01.VertexCover.pdf (2017 version)
Extra Reference: MVC @ VisuAlgo (the unweighted version)
Understanding Unsolvable Problem
(Re)-Introduction to the Min-Vertex-Cover problem (CS3230 review) and the 3C2 idea

PS: Sat, 18 Aug 2018, 12-5pm (SoC homecoming)
PS1-Art Gallery+, out on Wed, 15 Aug 2018, 13.45pm
A machine will help Yohanes/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 27/08/2018 00:00
02,
20-24
Aug
Not Started Public holiday on Wed, 22 Aug 18 (Hari Raya Haji)
CS4234 second class on this day is cancelled
and replaced with a make up class.


Make up class (due to missing Week 02+04)
is on Sat, 25 Aug 2018, 10am-12pm @ COM1-0204

02.LPIntro.pptx, 02.LPIntro.pdf (2016 version)
Extra Reference: MVC @ VisuAlgo (the weighted version)
Extra Material: 02.ExcelSample.xlsx, 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,
27-31
Aug
T01.pdf, T01-ans.pdf (see IVLE)
The Intro COP:
Min-(Weight)-Vertex-Cover
(I)LP, Max-Clique, and PS1 discussion
03a.SetCover.pptx, 03a.SetCover.pdf (2016 version)
Another Combinatorial Optimization Problem (COP): Min-Set-Cover

03b.SteinerTree.pptx, 03b.SteinerTree.pdf (2016 version)
Yet another COP: Steiner-Tree (3 variants)
Extra Reference: Steiner Tree @ VisuAlgo (the general/graph version)
PS1 due on Sat, 01 Sep 2018, 07.59am (5%)
PS2-Rubble+, out on Sat, 01 Sep 2018, 08.00am
Also on Mooshak
Sat, 01-08 Sep 2018, (IOI 2018 @ Tsukuba, Japan)
Steven (lecturer/SGP IOI team leader), Wei Liang (TA/International Scientific Committee member), and Ranald (student/International Technical Committee member) will not be available...
04,
03-07
Sep
No tutorial Steven (lecturer) and Wei Liang (tutor) will be in IOI 2018, Tsukuba, Japan
No Lecture and Tutorial this week and no make up class for Week 04 :O
But there is a self-reading assignment to prepare you for Week 05+06:
Self explore: TSP @ VisuAlgo and Max-Flow Visualization @ VisuAlgo.

PS2, continued
05,
10-14
Sep
T02.pdf, T02-ans.pdf (see IVLE)
PS1 Debrief
3 More COPs:
Min-Set-Cover
Steiner-Tree
Min-(Weight)-Feedback-Edge-Set
04.TSP.pptx, 04.TSP.pdf (2016 version)
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 due on Sat, 15 Sep 2018, 07.59am (5%)
Sat, 15 Sep 2018, ICPC Asia Singapore 2018 Preliminary Contest
This also doubles as NUS ICPC Team Selection Contest
Some problems there may be relevant to CS4234,
e.g. those that say 'maximize that' or 'minimize this'
06,
17-21
Sep
T03.pdf, T03-ans.pdf (see IVLE)
PS2 Debrief
2++ More COPs:
Travelling-Salesman-Problem
Max-Independent-Set
05.MaxFlow.pptx + 06.FFAnalysis.pptx (flipped classroom)
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
PS3-Mini Researcher, out on Wed, 19 Sep 2018, ~10.30am
PS3 is a written PS
Download the tasks here
Recess Week, 22-30 Sep 2018
We can take a break this week :)
07,
01-05
Oct
T04.pdf, T04-ans.pdf (see IVLE)
Back to a P optimization problems: Max-Flow
Max-Cardinality-Bipartite-Matching
Max-Independent(/Edge-Disjoint)-Path
Min-Cut
Alternative Ford Fulkerson's analysis
07.PushRelabel.pptx
Introducing the Push-Relabel Algorithm
Sample (manual) execution
(no VisuAlgo page yet involving Push-Relabel)
Analysis of Basic Push-Relabel Algorithm
PS3, continued
08,
08-12
Oct
T05.pdf, T05-ans.pdf (see IVLE)
Assignment-Problem
Discussion about O(n3) Push-Relabel algorithm
Midterm test preparation
PS3 (written) submission (during tutorial)
Midterm Test (25%)
Material: Week01-06, excluding Lecture 7 Push-Relabel, but including T05
Including stuffs from PS1-3 (PS3 task 3 style question appears)
(PS4 exposure is good to have but not crucial; only ~20% questions on Max-Flow)
Dinic's algorithm is not yet written properly in L5/6 ppt but can be reviewed here
There are more proving questions this time
Open book (no restriction on this)
Only one constraint: No electronic device (except normal calculator)
Midterm test paper (S1 AY 2016/17),
Midterm test paper (S1 AY 2017/18),
Midterm test paper (S1 AY 2018/19).
PS3 due on Mon, 08 Oct 2018 (5%)
(submit hardcopy to Weiliang during your T05)

PS4 Flows, out on Mon, 08 Oct 2018, 08.00am
The last one on Mooshak
09,
15-19
Oct
T06 (no new question)
Midterm Test Debrief
Solutions and common mistakes of the paper
will be discussed in tutorial but the solution file
will not be uploaded publicly
(see password-protected IVLE Workbin)
Scripts will be returned during tutorial
You can also ask stuffs about ongoing PS4 during T06
08.Matching.pdf
Introduction to (Weighted) Max-Cardinality-(Bipartite)-Matching Problem
Max-Flow, Augmenting Path Algorithm++, Hopcroft Karp's/Dinic's Algorithm
Overview of Min-Cost Max-Flow, Hungarian, and Edmonds's Matching Algorithm
Graph Matching Visualization @ VisuAlgo

PS4 due on Sat, 20 Oct 2018, 07.59am (5%)
10,
22-26
Oct
T07.pdf, T07-ans.pdf (see IVLE)
Discussion about Graph Matching problems/algorithms
Application of Matching/Max-Flow on two NP-hard COPs
Two other applications of (Weighted) (Bipartite) Matching
09.StochasticLocalSearch.pdf
Introduction to Stochastic Local Search (SLS)
Paradigm change, SLS Characteristics,
No proof, just experiments...
Mini-Project: Local Search, start on Mon, 22 Oct 2018
Preview on Mon, 22 Oct 2018
Proper launch during Lecture 09
Download S1 AY 2018/19 tasks here.
11,
29 Oct-
02 Nov
T08.pdf, T08-ans.pdf (see IVLE)
Discussion about Stochastic Local Search
Using one of Mini Project topic as the context
10.Meta-heuristics.pdf
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,
05-09
Nov
T09.pdf, T09-ans.pdf (see IVLE)
Discussion about SLS DTP
Mini Project progress discussion

"Active in Class" achievement will be finalized this week
Tutorial Participation Marks given
(5%)
11.SLS-DTP.pdf
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

PS: Deepavali, 06 Nov 2018 (Tue)
Does not clash with CS4234 class
Mini-Project, continued
ICPC Asia Jakarta 2018
Steven and a few other students outside CS4234 has competed in ICPC Jakarta 2018, Fri 09-Sat 10-Sun 11-Mon 12 Nov 2018
Result: 3rd, 12th, and 20th out of 74 teams.
No CS4234 class should be affected
Wei Liang is still present for the last tutorial T10
13,
12-16
Nov
T10.pdf, T10-ans.pdf (see IVLE)
SLS Design and Tuning Problem
Final assessment preparation
(also see links of past two final papers below)
Final class photo
First 1.5 hour: Mini Project Presentations
By 9 project groups
At most 9x5 = 45 minutes + buffer

Closed by:
Invitation to do PhD in algorithm... :)
Module review, and
Final assessment preview
Mini-Project due on Wed, 14 Nov 2018, 11.59am (15%)
Before last lecture,
you will present your work during the first hour of last lecture
ICPC Asia Nakhon Pathom 2018
Gan Wei Liang (TA), Ranald Lam Yun Shao (student), and Nguyen Tien Trung Kien (last year CS4234 student) has competed in ICPC Nakhon Pathom 2018, Thu 15-Fri 16-Sat 17-Sun 18 Nov 2018
Result: 1st and 3rd out of 69 teams.
No CS4234 class should be affected
Study Week
Final Assessment Consultations (per request)
Final Assessment, Tue, 27 Nov 2018 (EV, 5-7pm SGT), Venue: COM1-02-06 (SR1) (35%)
Past Papers:
Final paper (S1 AY 2016/17),
Final paper (S1 AY 2017/18).
ICPC Asia Yangon 2018
Bay Wei Heng, Muhammad Irham R B Z, and Raynold Ng Yi Chong (CS4234 students) will compete in ICPC Asia Yangon 2018, Fri 07-Sat 08-Sun 09-Mon 10 Dec 2018
No CS4234 class should be affected
ICPC Asia Singapore 2018
ICPC Asia Singapore 2018, Wed 12-Thu 13-Fri 14 Dec 2018

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. MPE: Given to students who got CS4234 via MPE (30 July 2018), i.e. the early birds...
  2. Bid (Round): Given to students who bid CS4234 via CORS (late July-early August 2018) instead of MPE-ing it during early July 2018 (closed after round 3B; Master/PhD student do not have to bid but will be classified here anyway)
  3. I Say Hi: Given to students who reply Steven's first proper welcome email regarding their reasons for taking CS4234 (sent on Tue, 14 August 2018, 11.42am); It will help Steven in planning the third iteration of this module (closed after the first lecture)
  4. Kiasu (#): Given to the first 7 students who solve all subtasks of PS1-Art Gallery+
  5. In FB: Given to students who are already in CS4234 FB group (closed after tutorial 01)
  6. Spanning Tree Master (#): Given to the first 7 students who solve all subtasks of PS2-Rubble+
  7. Mini Researcher (#): Given to only 4 students who have ≥ 90 points in PS3 (written)
  8. Flows Like Water (#): Given to the first 7 students who solve all (different) tasks of PS4-Flows
  9. Test Master (#): Given to the top 7 students who have the highest Midterm Test scores
  10. 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)
  11. Future Algorithm Researcher: Given to top 3 project groups who perform well in their mini project about SLS experiments on two (NP-)hard COPs
  12. 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
No Tut Grp TSP MWVC Student Name Achievements