DISCRETE OPTIMIZATION
MATH 258B, course information

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

  1. (*) Korte, B. H. Vygen, J. ``Combinatorial optimization : theory and algorithms'' Springer 2018 (online edition!)

  2. (*) J.A. De Loera, R. Hemmecke, and M. Koeppe, "Algebraic and Geometric Ideas in the theory of Discrete Optimization".
    MOS-SIAM book series on Optimization, volume 14, 2013 (online edition !)

  3. W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver. "Combinatorial Optimization", Wiley. 2000.
  4. A. Schrijver. "Theory of Linear and Integer Programming", Wiley. 1987.

  5. D. Bertsimas and R. Weismantel, ``Optimization over the integers'', Dynamic Ideas, 2005.

  6. C. Papadimitriou and K Steiglitz, Combinatorial Optimization, Dover 1999 (reprint of 1982 edition).

  7. E Lawler et al: "The traveling salesman problem: A guided tour of combinatorial optimization". Wiley, 1990.

  8. (*) Paschos, V. Th (ed) "Applications of combinatorial optimization", Wiley 2014.

  9. Gusfield, D. "Integer linear programming in Computational and systems biology", Cambridge 2019.

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:

    (Part I) What is Discrete Optimization and why study it? Through Examples and the 4 Key Models (3 weeks)

    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!!