Meetings: MWF 1:10-2pm, 117 Olson.
Instructor: Prof. Jesús A. De Loera.
Email: deloera@math.ucdavis.edu
Phone: (530)-554-9702
Office hours: MWF 2:10-3:00pm or by appointments. Please feel free to ask questions via email too. I will be in my office 1013 PSEL Building.
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 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 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, combinatorics, number theory, algebraic
geometry, topology, and more. So it is a sophisticated field of research.
This 10 week course will have three parts, here are the more detailed contents:
We introduce the subject through applications 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 Graphs, Networks, Matroids, and Polyhedra, the 4 key models used in combinatorial optimization to model on highly
structured situations:
Networks. Maximum Flow/ Minimum-Cost Flow Problems.
Optimal trees, paths, and matchings in graphs.
Set covering, set packing, knapsack problems.
Matroids and Submodular functions.
The mother of all the models: polyhedral models.
An illustrative example: the Traveling salesperson polytope.
Another illustrative example: the Matching polytope
(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)
(Part III) Advanced methods (3 weeks)
The final part of the course introduces breakthroughs from the past 15 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 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 to 4 hours per hour of class.
The main prerequisites are full confidence with linear algebra, real analysis, combinatorics, and probability, say 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 take-home exams, 35 points each.
Challenges include 10 to 12 problems (2-3 points each). Problems will be both
theoretical and computational
(e.g., some basic programming will be a must).
I will drop your lowest grade out of three, with a total of up to
70 points. I do not take late submissions!
AND!
(B) A final exam/project (30 points, due on final exam March 19, 2019 8:00AM).
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.
Please remember that NO late submissions will be accepted!!