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

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.

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.

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

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