2015S: Optimization (MAT 168)
Instructor: Prof. Matthias Köppe (office: 3143 MSB; email: mkoeppe+168@math.ucdavis.edu; office hours: see faculty office hours listing)
TA: Yuan Zhou (office: 3206 MSB; email: yzh@ucdavis.edu; office hours: Thursdays 3:10-4 pm)
Time and Location
see registrar's class list
Textbook
Robert J. Vanderbei, Linear programming foundations and extensions
Either the most current, 4th edition, ISBN-13: 978-1-4614-7629-0.
- Available electronically (as a PDF file) via the UC Davis Library at http://link.springer.com/book/10.1007/978-1-4614-7630-6
- (If you're connecting from off-campus, you'll need to use the UC Davis Library VPN.)
- Hardcopy available in the UC Davis Bookstore (but see below).
Or the older 3rd edition, ISBN-13: 978-0387743875
- Available electronically (as a PDF file) via the UC Davis Library at http://dx.doi.org/10.1007/978-0-387-74388-2
- (If you're connecting from off-campus, you'll need to use the UC Davis Library VPN.)
- Because of UC Davis's contract with the publisher, you can also order a print copy (soft cover) for $24.95 at the above link.
- New/used copies should be available from various vendors.
Topics
We will mostly follow the department syllabus.
We will cover one additional topic not on the department syllabus:
Integer linear optimization.
Grading
10% Class participation*, including in-class quizzes
20% Homework (including proof, modeling, programming exercises)
30% Midterm exams
40% Final exam
There will be two midterm exams. The lower grade of the two midterms
will be dropped.
Homework will be announced on SmartSite. No late homework will be
accepted, unless there is a documented emergency. The lowest score of the homework series will be dropped.
* Lectures will be interactive. I will ask questions on material from previous lectures and the required reading, and general questions that require to actively follow the current class.
Homework and announcements will appear on SmartSite. Auditors: If you would like to audit this class, send me your UC Davis id, and I can add you to SmartSite.
Exam Dates
Midterm 1 (in class): Friday, April 24
Midterm 2 (in class): Friday, May 15
Final exam: as announced on MyUCDavis
Modeling/Computational Homework Execrcises
Homework will include proof exercises, modeling/computational
exercises and programming exercises.
If you don't have an account on the department computers, you need to get a class
account from http://www.math.ucdavis.edu/comp/class-accts
We will be using the ZIB Optimization Suite (SCIP, SoPlex, ZIMPL) in class.
Please read the ZIMPL (optimization modeling language) documentation at:
http://zimpl.zib.de/download/zimpl.pdf
A version of the software is installed on the departmental computers in the directory ~mkoeppe/public/258b
Type
~mkoeppe/public/168/scip
to start the SCIP shell.
You can read ZIMPL models by typing
read MODELFILE.zpl
Use the interactive documentation of SCIP by typing
help
to learn about SCIP.
Please follow the examples in the ZIMPL documentation using SCIP.
You can also install SCIP on another computer. The download page (source and precompiled binaries) is here: http://scip.zib.de/#downloadPrecompiled versions for Windows and Linux are available. I don't know whether Mac OS X is supported, but you can try compiling the source code.
Programming Exercises
There will also be programming exercises as part of the homework. They can be completed in a high-level programming
language of your choice.
Additional Reading
The following books are useful additional reading.
- Jiri Matousek and Bernd Gärtner: Understanding and Using Linear Programming, Springer, 2007
- Available as an electronic text at http://dx.doi.org/10.1007/978-3-540-30717-4 (If you're connecting from off-campus, you'll need to use the UC Library VPN.)
- Chapter 4 provides a nice introduction into the polyhedral geometry behind linear optimization and the simplex method.
- 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