2014W: MAT 258B Discrete and Mixed Integer Optimization

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

More information will appear here shortly.

258B is still listed with the old title "Variational Analysis" in the course catalog.
The new 258B has a completely changed syllabus (see below).

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

This course will be very different from 258A "Numerical Optimization". 

Course Time: MWF 0210-0300 PM 
Room: PHYSIC 130
Instructor: Matthias Köppe


Office hours: WF 3-3:30 or by appointment.

Syllabus:

Grading is based on homework (70%) and, at your choice, a final project or a take-home final (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


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.

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

  • Linear Programming: Foundations and Extensions by Robert Vanderbei


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