2014S: MAT 280 Topics in Modern Convex and Mixed-Integer Optimization

Prerequisites: There are no graduate-level prerequisites for this course. In particular, it is independent of MAT 258A "Numerical Optimization" and MAT 258B "Discrete and Mixed Integer Optimization". If you want to learn the basics of polyhedral theory and linear optimization thoroughly (we do review everything as needed), I recommend taking or auditing class MAT 168 (Prof. A. Fannjiang, MWF 3:10-4) concurrently.

Course Time: MW 10:00–11:25.

Room: 2112 MSB

Instructor: Matthias Köppe

Office hours: MW after class (11:30-12) or by appointment.

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

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

Grading: This class is intended to expose graduate students to current research topics in optimization. Every registered student is required to present a topic in class and produce a corresponding write-up. The topic could be a paper from the recent research literature; there are also opportunities for research projects. Suggestions for topics are made in class and via announcements on SmartSite.

Topics:

We study modern techniques of convex and mixed integer optimization and their applications. The overarching theme linking these cutting-edge topics: Structure of projections of high-dimensional convex sets.

Tentative schedule:

Weeks 1–4: Extended formulations (linear and semidefinite) for combinatorial optimization problems

Guest lecture (Monday 4/14, 10:00) and seminar talk (Monday 4/14 12:10) – Dr. Thomas Rothvoss (U. Washington), The match­ing poly­tope has expo­nen­tial exten­sion complexity

Literature:

[EF1] OPTIMA 85, Mathematical Optimization Society Newsletter, issue 85, April 2011. http://www.mathopt.org/Optima-Issues/optima85.pdf

[EF2] M. Conforti, G. Cornuejols, and G. Zambelli, Extended Formulations in Combinatorial Optimization, Annals of Operations Research 204 (2013) 97-143. doi:10.1007/s10479-012-1269-0 (via UC Library). Survey with many references.

[EF3] V. Kaibel, S. Weltge, Lower Bounds on the Sizes of Integer Programs Without Additional Variables, arXiv:1311.3255 [math.CO]

[EF4] P.-F. Tsai, Tight Flow-Based Formulations for the Asymmetric Traveling Salesman Problem and Their Applications to some Scheduling Problems, Dissertation, Virginia Tech, 2006, http://scholar.lib.vt.edu/theses/available/etd-05232006-195259/unrestricted/dissertation_peifang_tsai.pdf

[EF5] F. Vanderbeck, L. Wolsey, Reformulation and Decomposition of Integer Programs, in: 50 Years of Integer Programming 1958–2008, doi:10.1007/978-3-540-68279-0_13 (via UC Library)

[EF6] A. Saxena, P. Bonami, J. Lee, Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, Math. Program. 130 (2011), 359–413, doi:10.1007/s10107-010-0340-3 (via UC Library)

[EF7] S. Iwata, N. Kamiyama, N. Katoh, S. Kijima, Y. Okamoto, Extended Formulations for Sparsity Matroids, arXiv:1403.7272 [math.CO]

[EF8] G. Braun, S. Pokutta, The matching polytope does not admit fully-polynomial size relaxation schemes, arXiv:1403.6710 [cs.CC]

[EF9] V. Kaibel, S. Weltge, A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially, arXiv:1307.3543 [math.CO]

Weeks 4–7: Geometry of compressive sensing (Tao, Donoho, Candès, ...)

Guest lecture (Monday 5/5, 10:00) – Dr. Thomas Strohmer (UC Davis, Mathematics)

Literature: The lecture will be based on the recent book [CS1]. See www.compressedsensing.com for an extensive bibliography.

[CS1] S. Foucart, H. Rauhut: A mathematical introduction to compressive sensing, Birkhäuser, 2013. http://link.springer.com/book/10.1007%2F978-0-8176-4948-7

Weeks 7–9: Infinite-dimensional relaxations of mixed-integer optimization problems (Gomory, Johnson, ...)

Literature:

[IR1] A. Basu, M. Conforti, G. Cornuéjols, and G. Zambelli, A counterexample to a conjecture of Gomory and Johnson, Mathematical Programming Ser. A 133 (2012), 25–38.

[IR2] A. Basu, R. Hildebrand, and M. Köppe, Equivariant perturbation in Gomory and Johnson’s infinite group problem. I. The one-dimensional case, eprint arXiv:1206.2079 [math.OC], 2012.

[IR3] A. Basu, R. Hildebrand, M. Köppe, and M. Molinaro, A (k + 1)-slope theorem for the k-dimensional infinite group relaxation, SIAM Journal on Optimization 23 (2013), no. 2, 1021–1040, doi:10.1137/110848608.

[IR4] M. Conforti, G. Cornuéjols, and G. Zambelli, Corner polyhedra and intersection cuts, Surveys in Operations Research and Management Science 16 (2011), 105–120.

[IR5] J.-P. P. Richard and S. S. Dey, The group-theoretic approach in mixed integer programming, 50 Years of Integer Programming 1958–2008 (M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, eds.), Springer Berlin Heidelberg, 2010, pp. 727–801, doi:10.1007/978-3-540-68279-0_19, ISBN 978-3-540-68274-5.

Week 10: Graver basis techniques for exponential-size integer optimization problems (Onn, ...)

We focus on the convex integer maximization case, based on projections and controlled edge directions [GB1, Chapters 2, 3.3.3], [GB3]. The state of the art in Graver-based convex integer minimization can be found in [GB2, Chapters 3–4]. Some open problems in this area (S. Onn).

Literature:

[GB1] Shmuel Onn, Nonlinear Discrete Optimization, Zurich Lectures in Advanced Mathematics, European Mathematical Society, 2010. e-book (free).

[GB2] Jesús A. De Loera, Raymond Hemmecke, and Matthias Köppe, Algebraic and Geometric Ideas in the Theory of Discrete Optimization, SIAM, 2012. e-book (via UC Library).

[GB3] Michal Melamed, Shmuel Onn, Convex integer optimization by constantly many linear counterparts, Linear Algebra and its Applications, 2014, doi: 10.1016/j.laa.2014.01.007 (via UC Library).

Background reading:

On Combinatorial Optimization (a subfield of discrete optimization).

On Integer Optimization:

  • Bertsimas, Weismantel: Optimization over the Integers, 600 pages, Hardcover, ca. $90
  • 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 use this textbook in 258B.
    • 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.
  • 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:

  • 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

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