2018w-mat-258b-discrete-and-mixed-integer-optimization

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 (50%), a substantial final project (40%), and peer-grading duties (10%). 

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 according to the Department syllabus:
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

I will deviate from the syllabus where it makes sense to cover some recent developments

Homework and other announcements

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

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

Our textbooks:

1) Bertsimas, Weismantel: Optimization over the Integers, 600 pages, Hardcover, ca. $90
Should be available in the bookstore; no e-text available unfortunately.

2) Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, Integer Programming, Graduate Text in Mathematics, Springer 2014, http://link.springer.com/book/10.1007%2F978-3-319-11008-0

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

Other textbooks on integer optimization:

  • 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.

Additional reading:

On Combinatorial Optimization:

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

  • 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.

On Mixed-Integer Nonlinear Optimization and Global Optimization:

  • 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


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



Comments