CS4234 - Optimisation Algorithms

Introduction

Overview (from Dr Seth Gilbert's version): 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) AY2017/2018, should Steven is assigned to teach this module again (TBC), should be similar to the past 2 AYs: ~40.

Useful information to help you decide on whether you should register for CS4234 (see CS4234 in nusmods.com, no review though) in S1 AY 2017/2018:

  1. It will be Steven's second iteration. The first iteration went relatively well and all known weaker spots will be improved in the second iteration. Steven did his PhD thesis around this topic more than 11 years ago and teaching the first iteration has refresh his own knowledge of this topic. VisuAlgo is currently being enhanced to include some NP-hard/complete topics too. Hopefully the second iteration will run even better than the first :).
  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.
    His 'Dr' title was obtained after ~6 years working on NP-hard Combinatorial Optimization Problems (2004-2010)...

    Teaching Assistant (TA): Hopefully for the second iteration, Steven can get ONE (1) eligible Teaching Assistant to help him run the second iteration instead of 100% himself in the first iteration.
    Machines, e.g. Mooshak, VisuAlgo, and Kattis will continue to be used to help him run this module...

    Rating (out of 5.00) Aug-Nov 2017 (n=??/??) Aug-Nov 2016 (n=23/40)
    Module feedback Hopefully 4.00 (slightly above CS dept average)
    Module difficulty Hopefully just a bit 4.13 (slightly harder than CS dept average)
    Steven's teaching Hopefully 4.53 (above CS dept average)

Syllabus

Steven will improve his second iteration of CS4234 with the following lesson plan (initially derived from Dr Seth Gilbert's version of S1 AY 2015/16):

  • Part 1 (about 4 weeks): Introduction to Combinatorial Optimization:
    1. Some NP-hard optimization problems: Min-Vertex-Cover (2 variants), Max-Clique, Min-Set-Cover, Steiner-Tree (3 variants), Traveling-Salesman-Problem (4 variants)
    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
    2. Analysis of various Augmenting Path heuristics for Ford Fulkerson's Algorithm
    3. The Push-Relabel Algorithm
    4. (Basic) Max Flow Visualization @ VisuAlgo
    5. Graph Matching Algorithms
    6. (Basic) Bipartite Matching Visualization @ 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. 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 (we will skip some complicated 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 (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: With ~40 students, a kind of weaker Bell Curve system will be used...
Q: Will this module flocked by students who have (very) good CS3230 grades?
A: Not 100% true, but indeed many of the first iteration students have reasonably strong interest in algorithm (thus reasonably good CS3230 grades and also good grades on previous related algorithm modules)
Q: How different will your version be compared to Dr Seth Gilbert's version?
A: The second iteration will improve on the relatively successful first iteration. Minor local changes are: (Slightly) less coding, (slightly) better proof presentation, (slightly) less competitive than the first iteration.
Q: Will there be some form of coding in this course?
A: The lecturer is (or was?) a competitive programmer. So yes, there will be implementation side of the various optimization algorithms that we discuss in class. You will try 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.17 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 algorithmic problems that do not have efficient solutions (thus not suitable and not included at all in my Competitive Programming book, not in the CP3.17 edition and likely also not in future edition(s)). Introduction to Algorithms (by CLRS, the typical textbook used in CS3230) and Algorithm Design (by Kleinberg and Tardos) are also recommended. Steven will also 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

The CS4234 syllabus will be delivered over 13 weeks, except on Week 02 and Recess Week.
There is an important schedule deviation on Week 01 due to Public Holiday on Tuesday, 9 August 2016 and Steven's absence on Week 02 due to IOI 2016.

Week Lecture
Tue 12-2pm
COM1-0204 (no webcast facility here)
Cells with ready course material are highlighted with light blue color, past classes are highlighted with khaki color, current week is highlighted with light green color, future classes are not highlighted
00,
Before
09 Aug
Not started
But please revise your CS1020+CS2010/CS2020 and CS3230
01a,
08-09 Aug
00.Introduction.pptx
01.VertexCover.pptx, 01.VertexCover.pdf
Extra Reference: Understanding Unsolvable Problem
(Re)-Introduction to the Min-Vertex-Cover problem (CS3230 review) and the 3C2 idea
Make up class due to public holiday on 9 Aug (National Day)
Date and Time: Monday, 08 August 2016, 6.30-8.30pm; Venue: COM1-0206 (SR1)
Webcast is available for those who cannot make it (you need to watch to do PS1)
Update: Only ~15/41 attended the first make up class
PS: Public holiday on Tue, 9 Aug 16 (Singapore National Day)
CS4234 first lecture will be affected.
01b,
10-12 Aug
02.LPIntro.pptx, 02.LPIntro.pdf
Extra Material: 02.ExcelSample.xlsx
Introduction to (Integer) Linear Programming + Relaxation
The Min-Weight-Vertex-Cover problem
Make up class due to Steven's absence on Week 02
Date and Time: Wednesday, 10 August 2016, 6.30-8.30pm; Venue: COM1-0206 (SR1)
Webcast is available for those who cannot make it (you need to watch to do PS1)
Update: Only ~22/41 attended the second make up class
02,
15-19 Aug
Steven is in Russia for IOI 2016
No class on Week 02, see the second make up class on Week 01
Do not forget to decide whether CS4234 with all those (NP)-hard problems are for you or not by end of Week 02...
03,
22-26 Aug
03a.SetCover.pptx, 03a.SetCover.pdf
Another Combinatorial Optimization Problem (COP): Min-Set-Cover
03b.SteinerTree.pptx, 03b.SteinerTree.pdf
Yet another COP: Steiner-Tree (3 variants)
04,
29 Aug-02 Sep
04.TSP.pptx, 04.TSP.pdf
Going deeper on this classic Travelling-Salesman-Problem
Extra Material: Someone made a movie out of this: Trailer, Movie website
05,
05-09 Sep
05.MaxFlow.pptx, 05.MaxFlow.pdf (give up for now)
Introduction to Max-Flow Problem
Ford-Fulkerson Algorithm
Max-Flow/Min-Cut Theorem
Max-Flow Visualization @ VisuAlgo
Public holiday on Mon, 12 Sep 16 (Hari Raya Haji): No CS4234 class is affected.
06,
12-16 Sep
06.FFAnalysis.pptx, 06.FFAnalysis.pdf (give up for now)
Analyzing the performance of Ford-Fulkerson
Other Augmenting Path Heuristics: Fattest-Path, Capacity-Scaling,
Edmonds Karp's Algorithm
Recess Week
WeSteven will really take a break from anything hard this week except 2 days for setting Midterm Test (but you will do PS3) :)
07,
26-30 Sep
07.PushRelabel.pptx, 07.PushRelabel.pdf (give up for now)
Introducing the Push-Relabel Algorithm
Sample (manual) execution
Analysis of Basic Push-Relabel Algorithm
08,
03-07 Oct
Midterm Test (25%)
Plan: Week01-06 material, excluding Lecture 7 Push-Relabel, but including T05
Including stuffs from PS1-3
Open book (no restriction on this)
Only one constraint: No electronic device (in any form except normal calculator)
The paper is here.
09,
10-14 Oct
08.Matching.pdf
Introduction to Max-(Cardinality/Weight)-(Bipartite)-Matching Problem
Max-Flow, Augmenting Path Algorithm++, Hopcroft Karp's Algorithm
Preview of Min-Cost Max-Flow and Edmonds's Matching Algorithm
(Bipartite) Matching Visualization @ VisuAlgo
10,
17-21 Oct
09.StochasticLocalSearch.pdf
Introduction to Stochastic Local Search (SLS)
Paradigm change, SLS Characteristics, No proof, just experiments...
11,
24-28 Oct
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...
PS: Public holiday on Sat, 29 Oct 16 (Deepavali); No CS4234 class is affected
12,
31 Oct-
04 Nov
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
13,
07-11 Nov
12.StevenPhDThesis
Steven's PhD thesis: 2004-2010, downloadable from NUS ScholarBank
Continuation of Lecture 11
This time showcasing TSP and LABS that you will need for Mini Project:
More FL/ST insights; More on SLS implementation techniques
Invitation to do PhD in algorithm... :)
Closed with module review and final assessment preview
Study Week
Final Assessment Consultations (per request)
Final Assessment, Thu, 24 Nov 2016 (Morning), Venue: SR1 (35%)

Class Roster

Steven uses a small-scale gamification system in his version of CS4234.
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 students who reply Steven's first email regarding their reasons for taking CS4234; It helps Steven in planning this module (closed after first lecture)
  2. I Bid CS4234 (Round): Given to students who bid CS4234 via CORS (late July-early August 2016) instead of MPE-ing it during early July 2016 (closed after round 3B; Master/PhD student do not have to bid)
  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 subtasks of PS1-Art Gallery, way faster than the stipulated deadline, when Steven is away, and without going through tutorial 01
  5. Spanning Tree Master (#): Given to the first 7 students who solve all subtasks of PS2-Rubble, way faster than the stipulated deadline, and without going through tutorial 03
  6. Mini Researcher (#): Given to the top 75 students who are judged to have the best PS3 (written) submission
  7. Test Master (#): Given to the top 76 students who have the highest Midterm Test scores
  8. Flows Like Water (#): Given to the first 7 students who solve all tasks of PS4-Flows
  9. Active in Class (Reason): Given to the top 3 students per tutorial group who participated the most in our first 9 tutorial classes (Given on Week 10-11, 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 3 project groups who perform well in their mini project.
  11. Nowhere to Hide (Reason): Given to students who already remembered by Steven (basically everybody by Midterm Test, Tuesday, 04 October 2016)
Student Name