CS 4234 - Optimization

(Fall 2015)

NUS School of Computing

Prof. Seth Gilbert

Tuesday 12:00pm - 2:00pm

COM1-0204

News

November 25	Final exam (and solutions) posted.
November 18	Sample final exams from CS5234 posted.
November 5	All lectures notes and tutorials for the semester now posted.
October 20	Lectures notes for Weeks 9 and 10 posted. Mini-project information posted. E-mail me your project goals soon.
October 6	Midterm and solutions posted.
October 1	Notes from Week 7 posted, along with IVLE questions answered. Also, solution sketches for all problem sets are posted.
September 20	Old midterms from CS5234 (2013 and 2014) posted. Beware that the content covered may not be identical to CS4234 this year.
September 19	Week 6 lecture notes posted.
September 19	Week 5 IVLE questions and Week tutorial questions posted.
September 10	Problem set 5 posted. Lectures notes and tutorial questions for week 5 posted.
September 5	Solutions to Problem Sets 1-3 posted.
September 3	Problem set 4 posted. Tutorial questions from Week 4 posted. Lectures notes from Week 4 on TSP posted.
September 3	Tutorial questions from Week 3 and IVLE question answers from Week 3 posted.
August 25	Problem set 3 posted. Lectures notes for Week 3 posted. Please go fill out the IVLE survey before tutorial on Thursday: ask one question!
August 19	Problem set 2 posted. Lectures notes for Week 2 posted. I also posted some links to interesting papers on the Simplex method.
August 12	Problem set 1 posted. Lecture notes for Week 1 posted. Please fill out the background survey on IVLE.
August 11	First class!

Schedule

Below is the (very) tentative schedule for the course. I will modify the schedule as the course progresses. Problem sets will be posted below on this schedule as they become available.

Class Number	Date	Description
		Part 1: Introduction to Combinatorial Optimization
1	11/08	Introduction and logistics. The vertex cover problem. Lecture 1 notes (powerpoint) [Download] Vertex Cover notes (pdf) [Download] Problem Set 1 [Download] Problem Set 1 Solutions [Download]
2	18/08	Introduction to linear programming. Weighted vertex cover. Lecture 2 notes (pdf) [Download] Problem Set 2 [Download] Problem Set 2 Solutions [Download] Interesting papers: Smoothed analysis (and why Simplex is almost always fast in practice). A more accessible general interest article on smoothed analysis: here There are some simplex-like algorithms that are polynonial time. This one uses something called the shadow vertex method.
3	25/08	Set Cover and Steiner Trees Set cover notes (pdf) [Download] Steiner tree notes (pdf) [Download] Problem Set 3 [Download] Problem Set 3 Solutions [Download] Tutorial Questions Week 3 [Download] IVLE Questions Answered [Download] Interesting papers: How do you implement algorithms for set cover on very large data sets? See this paper here.
4	01/09	The Travelling Salesman Problem. Lecture 4 notes (pdf) [Download] Problem Set 4 [Download] Problem Set 4 solution sketches [Download] Tutorial Questions Week 4 [Download]
		Part 2: Network Flows and Matching
5	8/09	Introduction to Maximum-Flow / Minimum Cut Lecture 5 slides (pdf) [Download] Lecture 5 handwritten notes (pdf) [Download] Tutorial questions [Download] Problem Set 5 [Download] Problem Set 5 solution sketches [Download] Week 5 IVLE Questions answered [Download]
6	15/09	Analyzing the performance of Ford-Fulkerson: Fattest-Path, Capacity Scaling Lecture notes (handwritten) [Download] Asymmetric TSP notes [Download] Tutorial questions [Download] CS5234 2014 Mid-term [Download] CS5234 2014 Mid-term solutions [Download] CS5234 2013 Mid-term [Download] CS5234 2013 Mid-term solutions [Download]
Break	23/09	No class: Mid-semester break
7	30/09	The Push-Relabel Algorithm Lecture notes (handwritten) [Download] Week 7 tutorial questions (from old midterms/exams) [Download] Week 7 IVLE questions answered [Download]
8	06/10	Midterm exam Midterm [pdf] Midterm solutions [pdf]
		Part 3: Continuous Optimization
9	13/10	Gradient descent and logistic regression Lecture notes (handwritten) [Download] Mini-Project information: Instructions (read these first) [Download] 1. Social Networks [Download] 2. Airport Scheduling [Download] 3. Computational Biology [Download] 4. Cloud Computing [Download] 5. Fair Division [Download]
10	20/10	Meta-heuristics and more: Metropolis, Simulated annealing, Tabu search, and finding a minimum degree spanning tree. Lecture notes (handwritten) [Download] Tutorial questions [Download]
		Part 4: The Primal Dual Method
11	27/10	Linear Programming Duality Lecture notes on linear programming duality (beginning on page 12), including a review of some material from Week 2 and a preview of Week 12 (handwritten) [Download] Tutorial questions [Download]
12	3/11	The Primal Dual Method (and applications to weighted vertex cover and maximum weight matchings) Lecture notes on the primal-dual method (handwritten) [Download] Tutorial questions [Download]
13	10/11	Deepavali (No class)
		End of class
14	25/11	Final Exam (Evening) Final exam [pdf] and solutions [pdf]. Sample final exam from CS5234 2014 [pdf] and solutions [pdf]. Sample final exam from CS5234 2013 [pdf] and solutions [pdf].

Course Overview

Description

This course focuses on algorithms for solving optimization 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.

Grading

Grades in the course will be based on problem sets (including a mini-project), a mid-term exam, and a final exam. In determining your final grade, these components will be combined as follows:

Problem sets / Mini-project	40%
Midterm	25%
Final	35%

The last problem set will involve a small project that involves further exploring some of the ideas that we have covered during the class.

How to do well in the class (without burning out)

A few tips for doing well in this course without excessive amounts of stress:

• Problem sets are probably the most important part of the class. Most people learn best by doing, not by reading powerpoint slides or lecture notes. Plan to spend significant time on the problem sets.
• Start problem sets early. Work systematically in focused bursts. Expect to need multiple sessions to finish the assignments.
• Learn the material the same week it is presented (using your textbook, your classmates, and me to help understand what confuses you). If you do this, studying for the exams will amount to a tractable review. If you do not do this, studying will devolve into a mind-numbing slog.
• I am always happy to talk about the material, during office hours, or to chat about the tactical side of succeeding (time management, study skills, etc.). Drop by my office, or schedule a time to meet.

Course Logistics

Office Hours

For now, office hours are by apointment. Once the semester begins, I'll schedule regular weekly office hours (and update the website here).

Contact

To ask me small logistical questions, I prefer that you grab my attention immediately before or after class. For substantive content questions, schedule a meeting with me.

Problem Sets

There will be weekly problem sets in the first 2/3rds of the class. (I expect this will end up being 6-7 problem sets in total.) These problems sets will focus on algorithm questions: solving problems, devising algorithms, proving theorems.

Problems will be graded on a simplistic 0/1/2/3 scale: a 0 indicates minimal understanding (or a problem not completed); a 1 indicates some understanding but many mistakes or poor presentation; 2 indicates a satisfactory answer; a 3 indicates a perfect answer that goes beyond expectations. You should expect to get a 2 on most problems.

The following rules will help keep the problem set submission and grading process running smoothly:

• You must hand in a solution that is unique, consisting of your work alone. You may discuss high-level strategy with other students in the class. You may read the textbook, or other reference pages on general topics. However, the solution you hand in must be written by you alone, and any similarities to any other student's submission (or to any web page or solution on the web) will be considered cheating. It will be considered equally cheating whether you copy from someone else, or if someone else copies from you.

  Do not compare or share your solution with others.

• You may not read or use solutions found on the web for identical problems, whether from prior years of this class or from other classes elsewhere.
• You may talk to people about general strategies, and you may use reference material available on the web (e.g., Wikipedia, lecture notes from other classes, etc.). If you talk to anyone else or read any reference material, you may not take notes on your discussion. Afterwards, spend half an hour on facebook (or some equivalent activity), before working further on the problem set.
• You are encouraged to typeset your problem sets (and are especially encouraged to use Latex). However, you may submit your problem sets in any form that is clear and easily legible. You are also encouraged to include many pictures and diagrams and examples in your problem sets. It is perfectly acceptable to typeset the problem set and attach hand-drawn figures.
• Problem sets should be handed in no later than the beginning of class on the day they are due. You may bring a physical copy of the problem set to class to give to me before the lecture begins, or you may submit it electronically on IVLE.
• Problem sets not handed in by the beginning of lecture will be considered late, and 10% of the points deducted. Problem sets not handed until the day after the deadline will have an additional 10% deducted (leave late problem sets in the envelope by my door). Beyond this point, problem sets will not be accepted.

Some advice on problem sets:

• Answers to homework should be written at a level suitable for and to address the instructor. In other words, don't put in long explanation for trivial things.
• You will be graded not only on the correctness and efficiency of your answers, but also on your clarity. Therefore, it pays to make your answers more concise and clearer. Understandability of the solution is as desirable as correctness. Sloppy answers will be at a disadvantage. Learn to make appropriate definitions to make your answers more precise and concise.
• Solutions do not have to be type-set, but they have to be neat and readable. Do not waste your time beautifying your answers. If you want to spend more time, you should spend it on improving its clarity, understandability, and other aspects of its technical content.
• From a previous module, you can find some advice on proofs here.
• From a previous module, you can find a sample of what a good solution looks like here.

Exams

There will be one two exams in the course: a midterm and a final. The mid-term exam will be held in class on October 6. The final exam will be held on November 25. The final exam will be graded and returned to you by the end of the semester.

Academic Integrity

I take academic integrity seriously. To repeat the problem set instructions from above: the solutions you submit must be your own unique work. Any cases of cheating will be dealt with harshly: a first offense will result in at least a one letter grade deduction for the module (or potentially a zero for the entire module, depending on the severity). When in doubt, ask me what is allowed.