Meetings: The class takes place in 146 Olson Hall. Lectures will be recorded and posted online (typically by the end of the week).
Instructor: Professor Jesús A. De Loera.
email: jadeloera@ucdavis.edu
URL: http://www.math.ucdavis.edu/~ deloera/
Office hours : MW 4:00-5pm or by appointment.
My office is 1013 PDSB (physical and data science building).
Assistant: Anna Luo and Aidan Epperly
email: ayuluo@ucdavis.edu acepperly@ucdavis.edu
Office hours: Anna will be hosting one online office hour on Zoom each Tuesday 11am - 12pm (https://ucdavis.zoom.us/j/92259244323) and one in person office hour at MSB 3125 every Wednesday 2 pm - 3 pm.
Prerequisites: MAT 22AB, 127A or equivalent, mathematical maturity, and willingness to solve many exercises and use mathematical software.
Textbooks and other sources:
I do not use a single book as I try to incorporate fresh material to this exciting topic. I will provide
extra notes and slides too. The main textbooks I use are freely available online through UC Davis library,
It is not necessary, but if you wish, you can purchase them online too:
1) Robert J. Vanderbei, Linear programming foundations and extensions, Kluwer 3rd edition
ISBN-13: 978-0387743875
The book is available electronically via the UC Library at http://dx.doi.org/10.1007/978-0-387-74388-2
library link too
2)
Jiri Matousek and Bernd Gärtner: Understanding and Using Linear Programming, Springer, 2007.
A wonderful description of ideas and intuition! It is freely available as an electronic text at link to UCD library
3) Bradley, Hax, Magnanti: Applied Mathematical Programming. 1977.
A classic introduction to mathematical optimization with a strong emphasis
on applications.
Freely available from MIT's
intro to optimization web site .
NOTE: If you're connecting from off-campus, you'll need to use the UC Library VPN.
Software and Programming:
You need to get a class account from the math department
To register you will need to use the CRN of the course.
Most of my own in class demonstrations will be with MATLAB and the ZIB Optimization Suite (SCIP, SoPlex, ZIMPL).
You are free to use other softwares! There are many options.
Please read the ZIMPL (optimization modeling language) documentation at: http://zimpl.zib.de/download/zimpl.pdf
The software is installed on the Math department computers. But you have to login into the right machine!
ssh username@cube.math.ucdavis.edu
Once you are there type scip to start the SCIP shell. You can read your ZIMPL models by typing
read FILE_NAME.zpl
You need to first have FILE_NAME.zpl in the right directory and the right computer for this to work.
Your zpl files are created with a text editor like VI or EMACS. Do NOT use word processors (such as Microsoft WORD) for this task!
Use the interactive documentation of SCIP by typing help
You can also install SCIP on your own computer. The download page
(source and precompiled binaries) is here: scip.zib.de/download.shtml
Precompiled 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.
Description of the course: This course is an introduction to an exciting field of applied mathematics: Optimization and Mathematical Programming.
Mathematical Optimization is the part of applied mathematics that deals with finding the optimal choice among a large,
possibly infinite, set of possible scenarios determined by constraints (typically translated in the form of equations and inequalities),
with each scenario having a concrete cost or price. For instance, in a management or business problem, we might
want to maximize the profit or minimize the cost of an operation. When fitting experimental data we may want to
minimize the total deviation of observed data from predictions based on a model. When creating an electric network
we may want to minimize its vulnerability to attacks or maximize its capacity of transmission. In designing an
automobile, we might want to maximize the strength of the body or minimize its weight. Of course, optimization is
not just in essential in applications but also it is everywhere in pure math: For example, linear optimization was
used in the recent proof of the Kepler's conjecture about efficient packing of balls in space and when studying protein
folding configurations of minimal energy are relevant.
The course intends to teach you 3 skills, thus the course has 3 components:
MODELING) How to model optimization problems mathematically and how to apply software to find solutions.
Applications in science, engineering, management, etc. (first midterm/project due at end of 3 weeks)
Material for this first part (weeks 1-3): Examples of optimization
models and motivation. Modeling techniques.
Applications include data science, game theory, finance, logistic and transportation, management science, bioinformatics, etc.
Mathematical programs, mixed-integer programming, linear and convex programs, network/graph models, non-linear non-convex problems,
game theory, multi-objective models. Introduction to solvers (SCIP,).
ALGORITHMS) How to use the algorithms to solve mathematical optimization models: (second midterm/project due end of week 6)
Material up to second part (weeks 4-6): Introduction to branch-and-bound for mixed-integer problems, cutting planes,
relaxations, a first view of linear programs and the simplex method, network flow graph algorithms, greedy and dynamic programming, heuristics.
Considerations of efficiency and computational complexity.
MATHEMATICAL THEORY) Learn to justify the correctness and performance of algorithms we used (Third and last midterm due end of week 10)
Material for third part (weeks 7-10): Convexity and Polyhedra, Farkas Lemma, Duality of linear programming, complementary slackness and optimality.
Primal vs. Dual Simplex method, Sensitivity analysis, Numerical-Implementation issues, Network flow problems. linear vs non-linear optimization.
Grading policy: Students can gain up to 100 points during the course:
I will assign grades based on the statistical curve of final points obtained by all students. Please note the following rules:
NO late work will be EVER accepted! Plan ahead!
Cheating will not be tolerated! You have been warned!
You can discuss with others, you can use AI, books etc, but you have to write your own solutions.
State explicitly your use of AI and who was your discussion partner(s) or any outside sources.
Finally, Mathematics is not an spectator sport, you need to work hard to learn! Dedicate time to thinking and studying.