Syllabus

Every Tuesday and Thursday from Jan 8 through April 22, no class on Jan 8 (instructor traveling), Jan 10 (instructor sickness), Feb 26 and 28 (instructor traveling), March 4 and 6 (Midterm Recess), and April 3 (Spring Recess). Time and location of 4 make-up classes will be announced.

Topics covered:

1. Introduction to graphs, paths, cycles, and trees


2. The shortest path problem: the Bellman-Ford and Dijkstra's algorithms, all-pair shortest paths; Applications: circuit design, hospital floor planning, etc.


3. The maximum flow problem: flows and pseudoflows, cuts and minimal cuts, residual networks, augmenting paths, flow decomposition, the augmenting path algorithm, the push-relabel algorithm, implementations; Applications: some computer vision problems


4. The bipartite mathing problem


5. Minimum cost flow and assignment problems: prices and reduced prices, assignment, cost and capacity scalings
6. The multicommodity flow and concurrent flow problems


7. Integer programming: branch-n-bound and branch-n-cut algorithms; Search algorithms: the genetic algorithm, the ant-colony algorithm, direct search algorithms


8. Integer programming software

Workload

1. Homework: There will be approximately four homework sets. You can discuss these assignments with classmates, but you must hand in your own final write-up.


2. Project: There will be one semester-wise project. The primary goal of this project assignment is for you to have hand-on experience of solving a practical problem. You will practise
• recognizing a practical problem as a combinatorial one;
• reducing the combinatorial problem and identifying its type;
• formulating the problem as one of those models taught in class;
• exploiting problem-specific structures;
• implementing a fast and robust solver.
In order to reduce your workload on writing computer codes, MATLAB/C/C++ code templates for basic data structures will be provided upon request.

The secondary goal is to provide a chance for you to make a professional oral and written presentation of results.

You will be asked to form groups of 1 or 2 students (2 students only if one cannot program in either MATLAB or C/C++) for solving the problem of designing a hospital. Each group should report progress, as well as any difficulties encountered, to instructor or TA.

Competitions: After midterm recess, a set of easy testing data will be used to evaluate the intermediate results of all groups. In early April, a set of hard testing data will be used to evaluate the final results of all groups, in terms of solution correctness and quality, as well as computing time. Final computer codes and written reports will be due by the end of April. Exceptionally novel results may be considered for further improvement and publication after the class. This project will account for 65% of the final grade.


3. Exam: no exams is currently planned.


4. Grading: Homework 25%, In-class Q&A's 10%, Project 65%.

Textbooks:

1. Primary textbook: Combinatorial Optimization by Cook, Cunningham, Pulleyblank, and Schijvier [find an inexpensive copy here]


2. Reference textbook: Network Flows by Ahuja, Magnanti, and Orlin [find a cheap copy here]

Notice on disability:

• Any student with a disability requiring accomodations in this class is encouraged to contact me after class or during office hours. All discussions will remain confidential. Additionally, students can contact the Disabled Student Services office in the Ley Student Center.