Meetings: MWF 3:10-4pm, 201 Wellman.
Instructor: Prof. Jesús A. De Loera.
Email: jadeloera@ucdavis.edu (you can ask questions about the course)
Office hours: Tuesday 2:10-3:00pm or by appointment.
Office 1013 PDSB Building (in between physics and chemistry buildings).
Textbooks: There is no required textbook. I prepare the class
based on many textbooks and journal articles (see sources below)
and I expect you will take notes, think about what I present, ask me
questions, and read more about it in the references listed.
Textbooks marked (*) are available for FREE online through UC Davis
Description: This is a graduate-level introduction to Discrete optimization (also often called Integer and Combinatorial Optimization).
This an an area of Applied Mathematics that considers the problem of finding the optimal element among a large, but finite (!), set of objects.
Each object is given a costs or value by an objective function. The goal is to minimize or maximize the function. Discrete optimization
has many kinds of applications: bioinformatics, telecommunications, scheduling, VLSI, data mining, and product distribution, to name just a few.
Discrete Optimization is at the core of making decisions using mathematics! Most important discrete optimization requires the use of many mathematical tools including combinatorics, graph theory, convex geometry, algorithms, probability, analysis, number theory, algebraic geometry, topology, and more. So it is a sophisticated field of modern research.
This 10 week course will have three parts, here are the more detailed contents:
We introduce the subject through applications, examples, and a
quick tour of famous problems and (some) software:
a) Optimal matchings: assignments, the stable marriage problem.
b) Optimal allocation: network flow problems, shortest paths and trees.
c) Optimal orders: Scheduling, strings, Genomics.
e) Optimal packings: Knapsack and bin-packing problems.
d) Optimal partitions: Clustering, image segmentation.
e) Overview of methods and discussion of final projects (Gurobi,ZIMPL).
Then we focus on five key objects Graphs, Networks, Matroids, Polyhedra and Lattices ,
these 5 objects are used in combinatorial optimization to model and compute.
NETWORKS (e.g., Transport and Flow Problems.)
GRAPHS (e.g., paths, matchings).
MATROIDS (e.g., optimal spanning trees).
POLYHEDRA and other convex sets.
LATTICES and Diophantine computing
(Part II) Polyhedral Combinatorics and Convexity (4 weeks)
The second part of the course will use convex and polyhedral combinatorics
to present a general modeling and algorithmic
framework to solve ANY combinatorial optimization problem.
Linear programs and Polyhedra.
Duality and Farkas Lemma.
Weyl-Minkowski Theorem
LP relaxations and roundings
Integrality of polyhedra: Complexity of algorithms. (NP-hardness).
Unimodular polyhedra
Integer Programming methods: Cutting plane theory
Branch and bound, branch and cut algorithms.
Lattices and Convex bodies (Minkowski's theorem, LLL algorithmm, flatness theorem)
Basic Complexity theory
(Part III) Advanced methods (3 weeks)
The final part of the course introduces breakthroughs from the past 10 years using advanced mathematical tools.
When all fails: Approximation Algorithms and Heuristics
Nullstellensatz, sums of squares, SDPs, and other approximations.
Integer programming in fixed dimension (Lenstra and generating functions).
Block-structured Integer Programs (Hilbert/Graver bases)
A taste of Mixed-Integer and Non-Linear Combinatorial Optimization
Pre-requisites and Expectations: This course is suitable for young graduate students in Applied Mathematics, Mathematics, CS, Statistics, and Engineering. The main goal is to introduce students to modern combinatorial optimization techniques used in practice through lots of exercises and assignments. On average, students will need to work 3.5 hours per hour of class.
The main prerequisites are full confidence with linear algebra, real analysis, combinatorics, and probability, at the senior undergraduate level. The course will have some programming too, so another pre-requisite is willingness to learn, on your own, new mathematical software. Familiarity with the theory of algorithms and complexity, graph theory, or linear programming is definitely a plus, but it is not a pre-requisite.
Computer resources Students will have to do some programming.
I will do all my examples in ZIMPL/SCIP, but you can program any other
solver.
Several solvers are installed in Math department and there
are course accounts for everyone. To obtain one, please go to
for class accounts.
There you will need to know the course CRN.
Grading policy: The final grades will be calculated using:
(A) Three long homeworks, 30 points each. Each homework includes a lot of problems problems (2-3 points each), so you have to do a minimum of 10 problems. Problems will be both theoretical and computational (e.g., some basic programming will be a must). But I hope you will want to do more to prepare for Quals etc. I will drop your lowest grade out of three, with a total of up to 60 points. I do not take late submissions!
AND!
(B) A final exam/project (40 points, due on finals week, 2019.
As a final project you will present a short investigation of a problem,
covering theory and practice (of your choice). You should prepare the report
as a job interview (include motivation, methodology, models, basic theory used,
computation and examples, pictures). I will suggest possible projects in class.
(C) All submissions of homework and final project are expected to be on a team of no more than 3 students. Please plan ahead.
Please remember that NO late submissions will be accepted!!