What will you do with your degree in mathematics? Chances are that you are looking forward to start a career in a company, in one of a wide variety of industries. It is a fact that many companies hire mathematicians because of their ability to analyze business processes (such as production, logistics, finances). We create mathematical models for the processes and use mathematical software to solve them. This allows us to make good (or even optimal) decisions on how to change these processes to make them better.
In this class you will learn about basic techniques of optimal decision making, which will help to prepare you for such a career. It is a self-contained class without any prerequisites other than familiarity with rigorous mathematics.
You will learn to use a convenient mathematical modeling language that allows to write down a mathematical model of a business process in the computer. We will then use mathematical optimization software to solve this model. This software is amazingly powerful, it will solve most models that we try within just a second. We will use this software as a black box only. (To learn what is inside, take MAT-168 in Spring, followed by a number graduate-level courses where we explain this exciting optimization technology...)
Some business processes, however, have an enormous complexity, which will create huge mathematical models. In these cases, just using the black box of mathematical optimization software will not be good enough. There are many exciting ways how to fix this. In this class, we will mostly be studying special cases, such as shortest route and network problems. For these special (but important) cases, we will show that there are beautiful and super-fast "combinatorial" algorithms that are much faster (and simpler!) than the black box. We will study mathematical proofs that establish that the algorithms are correct (always produce an optimal solution) and efficient.
For students who have already taken MAT-168 (Math. Programming), this class is also an excellent choice. You have already learned about network flows; we also cover this topic, but we introduce different algorithms (such as the primal-dual algorithm rather than the network simplex algorithm), so your knowledge will be extended.
For computer science majors, this class is also very beneficial, as we discuss important and fundamental combinatorial optimization algorithms, efficient data structures, and their complexity analysis.
If you have any questions on the class, please write an email
(mkoeppe@math.ucdavis.edu)
or stop by my office (MSB 3143), I will be happy to answer them.
Textbook: I will be teaching material that corresponds to selected chapters of the book Combinatorial Optimization, by William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver, which is also suggested reading for this class. It is not required to buy the book, as I will give out copies of my notes before each class.
Prerequisites: The class has no formal prerequisites. The class should be suitable for all math, computer science, and engineering majors. I will assume familiarity with rigorous mathematics, in particular the ability to follow and write mathematical proofs; also I will assume basic familiarity with a programming language of your choice.
Relation to other courses: This class complements, but is independent of MAT-145 (Combinatorics) and MAT-168 (Mathematical Programming).
Grading: Grading will be based on homework (20%), one programming project in the general-purpose programming language of your choice (20%), two 50-minute written midterms (30%; I drop the lower grade of the two midterms), and a final 50-minute written exam (30%).
I reserve the right to replace all or some of the in-class midterms and the final exam by take-home exams.
| Week | Topic | Chapter |
|---|---|---|
| 1 (Jan 6, 8) |
Decision Making, and the rôle of Mathematical Optimization. Deterministic vs. stochastic, continuous vs. discrete, linear vs. nonlinear, combinatorial vs. unstructured, single-criteria vs. multi-criteria optimization problems. Introduction to modeling languages and black-box optimization software, using the ZIMPL modeling language and the SoPLEX and SCIP solvers. | |
| 2 (Jan 13, 15) |
First combinatorial examples: The Shortest Path Problem; the Euclidean Traveling Salesperson Problem; the Euclidean Matching Problem. Their optimization models. Practical efficiency: Measuring the running time of black-box optimization software. |
1.1
1.2 2.2 |
| 3 (Jan 20, 22) |
What to do when the black box is too slow. A specialized algorithm for the Shortest Path Problem: Feasible potentials; Ford's algorithm. Correctness proof. Theoretical efficiency (complexity theory) in the Random Access Machine model of computation; asymptotic notation using Landau symbols ("big O"). Complexity analysis of the algorithm. |
2.2
9.1–9.9 |
| 4 (Jan 27, 29) |
More algorithms for the Shortest Path Problem: The Ford–Bellman algorithm, Dijkstra's algorithm. Correctness and efficiency of the algorithms. | 2.2 |
| 5 (Feb 3, 5) |
Mid-term exam I (written).
After the quiz: What to do when the specialized algorithm is too slow. Accounting for running time using a sampling profiler, on the example of a C implementation of Dijkstra's algorithm and the GNU Graph Profiler (gprof). The bottleneck in Dijkstra's algorithm for sparse graphs. Efficient datastructures: Binary heaps (priority queues). Revised running time analysis, revised implementation. |
2.2 |
| 6 (Feb 10, 12) |
Introduction to network flow problems. Maximum flows and minimum cuts. Auxiliary digraphs, and the augmenting path algorithm for the Maximum Flow Problem. Shortest augmenting path algorithm. |
3.1
3.2 |
| 7 (Feb 17, 19) |
Applications of Max-Flow–Min-Cut: Bipartite matchings and Kőnig's Theorem; flow feasibility problems. | 3.3 |
| 8 (Feb 24) |
Mid-term exam II (written) | |
| (Feb 26) |
Minimum-cost flows. Optimality conditions. A primal algorithm: The Augmenting Circuit Algorithm. |
4.1
4.2 |
| 9 (Mar 3, 5) |
The primal-dual algorithm for minimum-cost flows. Correctness and efficiency. | 4.3 |
| 10 (Mar 10, 12) |
A look at the Traveling Salesperson Problem. The cutting-plane method. Equivalence of separation and optimization. Separation of subtour constraints and comb inequalities. |
6.7
6.8 7.1–7.4 |
| (Mar 20) | Final exam (written), on Friday Mar 20, 3:30 pm. |
Slides of Lecture 2, Example ZIMPL file
Slides of Lecture 4, Models for the 6-city TSP
Homework (as announced in the lecture, due next Thursday): Study the ZIMPL manual carefully. Do the case study on the last slide of Lecture 4, on GPS navigation systems.
Slides of Lecture 6, Models, data, and scripts for the pen plotter problem
Homework (written) as announced in the lecture, due next Thursday, see the last slide of Lecture 6.
Slides of Lecture 7 (link corrected), Model of the matching formulation of the pen plotter problem
Homework (oral) as announced in the lecture, due this Thursday: Run the Ford algorithm for the two given examples.
Homework (written) as announced in the lecture, due next Thursday (Feb 5): Homework problems 1, 2, 3 at the end of the slides.
Additional, non-required homework (training for the 1st midterm): Do some of the modeling exercises from the copies I gave out. If you turn these in by Tuesday (Feb 3), I will grade/comment and return them by Thursday (Feb 5).
Announcement:
The first mid-term exam will be a take-home exam, given out on Thursday (Feb 5) and due Tuesday (Feb 10)
Homework (written) 4 problems as announced in the lecture, due next Thursday (Feb 19).
Programming homework: As announced in the lecture (see last slide of Lecture 13), due on March 17; data files are available here.
~mkoeppe/mat180/; note that it only works
on the 64-bit computers in the department. If you use one of the
computers in the undergraduate lab, you will need to use secure shell
to connect to another computer:
ssh point.math.ucdavis.edu
If you would like to use the software from home, assuming a Windows
box, use
the PuTTY ssh client to connect to one of the department computers.
Matthias Koeppe