Meetings: The lectures will be recorded in advanced and posted online (typically by 4pm MWF), so this
course will be taught mostly asynchronously.
You can watch the lecture whenever you want.
But I will give you a chance to ask questions and interact with me online (ZOOM)
Every MWF 4:00-6:00pm. These session will not be lectures nor office hours, they will be a
real conversation and discussion about
what you read, studied, thought, and tried. Come prepared!!
Instructor: Professor Jesús A. De Loera.
email: deloera@math.ucdavis.edu
URL: http://www.math.ucdavis.edu/~ deloera/
Online Synchronous meetings: MWF 4:00-6pm or by appointment.
Assistant: Zhenyang Zhang
email: zhenyangz@math.ucdavis.edu
Office hours: Tuesday: 1- 2:00pm (online)
Prerequisites: MAT 22AB, 127A or equivalent and a willingness to solve many exercises and learn 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 and recordings 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
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.
We will be using MATLAB and 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
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.
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 an statistical curve of 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 but you have to write your own solutions/code
State explicitly who was your discussion partner(s) or any outside sources.