Information on the graduate course "Discrete and Mixed-Integer Optimization".

There are no graduate-level prerequisites for this course. In particular, it is completely independent of 258A "Numerical Optimization".

Course Time / Room: see registrar's or department's class schedule

Instructor: Matthias Köppe

Office hours: see department office hours page

Syllabus:

Grading is based on homework (70%) and a substantial final project (30%). Solving homework will require ability to read and write mathematical proofs, and familiarity with a programming language of your choice. Knowledge of linear algebra and the basics of linear optimization (see below for resources on linear optimization for self-study) are required.

Topics:

Modeling techniques for integer and mixed integer optimization

Modeling languages

Optimization software

Branch-and-cut technology for combinatorial and mixed integer linear optimization

Cutting plane theory

Primal methods

Nonlinear branch and bound and outer approximation

Global optimization: Spatial branch and bound and convexification

Detailed syllabus

Homework and other announcements

I will be using SmartSite to announce reading, homework, and distribute grades.

Auditors: Please let me know your Kerberos id, so I can give you access to SmartSite.

Our textbook:

Bertsimas, Weismantel: Optimization over the Integers, 600 pages, Hardcover, ca. $90

Should be available in the bookstore.

Our textbook is a very up-to-date (2005), comprehensive, and accessible textbook that covers all aspects of integer and mixed-integer linear programming. It is used at MIT and other places for teaching Integer Programming at the graduate level.

I will supplement this by additional material on mixed-integer nonlinear optimization following the most recent developments on the research frontier.

Comparable textbooks:

• Laurence A. Wolsey, George L. Nemhauser, Integer and Combinatorial Optimization, 763 pages, Paperback, ca. $110
• A comprehensive, older (1988) text.
• Laurence A. Wolsey, Integer Programming, 264 pages, ca. $90-$130
• A gentle, and short, introduction to Integer Optimization aimed at the advanced undergraduate and master's level.
• Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, Integer Programming, http://link.springer.com/book/10.1007%2F978-3-319-11008-0
• This recent book (2014) will complement our textbook on some topics.

Additional reading:

On Combinatorial Optimization:

Combinatorial optimization is a subfield of discrete optimization, but not the emphasis in our class.

• William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver, Combinatorial Optimization
  • Christos H. Papadimitriou, Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity
  • A true classic. You can get a paperback of this one for ca. $14
• Bernhard Korte, Jens Vygen, Combinatorial optimization theory and algorithms, Springer, 2008
• Available through the UC Library as an e-text free of charge. (If you connect from off-campus, use the UC Library VPN.) You can also order a copy via SpringerLink for $25.

On Integer Optimization:

• Alexander Schrijver,Theory of Linear and Integer Programming, ca. $100
• An important reference for every researcher in Integer Optimization
• Michael Jünger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Laurence A. Wolsey (Editors): 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, Hardcover, 804 pages
• Among other things, this contains surveys on the most important current research directions in Integer and Nonlinear Mixed-Integer Optimization.
  • Jesús A. De Loera, Matthias Köppe, Raymond Hemmecke: Algebraic and Geometric Ideas in the Theory of Discrete Optimization, SIAM, 2012

On Mixed-Integer Nonlinear Optimization and Global Optimization:

• Duan Li, Xiaoling Sun, Nonlinear integer programming, Springer, 2006.
• Available through the UC Library as an e-text free of charge. (If you connect from off-campus, use the UC Library VPN.) You can also order a copy via SpringerLink for $25.
• Ivo Nowak, Relaxation and decomposition methods for mixed integer nonlinear programming, Birkh?user, 2006.
• Available through the UC Library as an e-text free of charge. (If you connect from off-campus, use the UC Library VPN.) You can also order a copy via SpringerLink for $25.
• Mohit Tawarmalani, Nikolaos V. Sahinidis, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications
• Christodoulos A. Floudas, Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications

For a background on linear optimization:

Most textbooks on linear optimization give sufficient background. Here are two examples:

• Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis
• Linear Programming: Foundations and Extensions by Robert Vanderbei
• Jon Lee, "A First Course in Linear Optimization", available from https://sites.google.com/site/jonleewebpage/home/publications/

Further resources:

• Bradley, Hax, Magnanti: Applied Mathematical Programming
• A general introduction to mathematical optimization, including integer linear optimization, from an applied point of view. This is a bit dated (1977), but still a good reading on the basic material.
• A re-typeset version of this 1977 MIT classic is available online as a full text

Software

• COIN/OR, version 1.3.1 ("CoinAll" package)
• This is installed on the Math computers in the directory ~mkoeppe/public/dest-1.3.1/bin
• If you want to install this on your own computer, you can download a binary distribution from http://www.coin-or.org/download/binary/CoinAll/
• IBM ILOG CPLEX 12.1
• This is installed on the Math computers, and is available as the command cplexte

If you don't have an account on the Math computers, you can request a class account by visiting http://www.math.ucdavis.edu/comp/class-accts