Previous years: 2020
This course focuses on analytical and computational tools for optimization. We will introduce least squares optimization with multiple objectives and constraints. We will also discuss linear optimization modeling, duality, the simplex method, degeneracy, interior point methods and network flow optimization. Finally, we will cover integer programming and branch-and-bound algorithms. A broad spectrum of real-world applications in engineering, finance and statistics is presented.
This course introduces analytical and computational tools for mathematical optimization. Upon successful completion of this course you should be able to:
- Model decision-making problems across different disciplines as least squares, linear and integer optimization problems.
- Apply the most appropriate optimization tools when faced with a concrete problem.
- Understand which algorithms are slower or faster, and which problems are easier or harder to solve.
All office hours will take place in Sherrerd Hall 123.
Name: Rajiv Sambharya
Oﬀice hours: Fri 9am - 10:30am
Name: Irina Wang
Oﬀice hours: Mon 2pm - 3:30pm
Name: Vinit Ranjan
Oﬀice hours: Tue 4pm - 5:30pm
All lectures will take place in Friend Center 006 on Tuesdays and Thursdays 1:30pm - 2:50pm. The schedule is as follows (subject to change):
|2||01/27||Solving linear systems in practice||02_lec.pdf 02_lec_ann.pdf||1 Out|
|3||02/01||Least squares||03_lec.pdf 03_lec_ann.pdf|
|4||02/03||Least squares data-fitting||04_lec.pdf 04_lec_ann.pdf||2 Out|
|5||02/08||Multiobjective least squares||05_lec.pdf 05_lec_ann.pdf|
|6||02/10||Constrained least squares||06_lec.pdf 06_lec_ann.pdf||3 Out|
|7||02/15||Linear optimization||07_lec.pdf 07_lec_ann.pdf|
|8||02/17||Piecewise linear optimization||08_lec.pdf 08_lec_ann.pdf||4 Out|
|9||02/22||Geometry and polyhedra||09_lec.pdf 09_lec_ann.pdf|
|10||02/24||Applications: data science, control, finance||10_lec.pdf 10_lec_ann.pdf|
|11||03/01||Simplex method||11_lec.pdf 11_lec_ann.pdf|
|12||03/15||Simplex method implementation||12_lec.pdf 12_lec_ann.pdf|
|13||03/17||Duality||13_lec.pdf 13_lec_ann.pdf||5 Out|
|14||03/22||Duality II||14_lec.pdf 14_lec_ann.pdf|
|15||03/24||Sensitivity analysis||15_lec.pdf 15_lec_ann.pdf||6 Out|
|16||03/29||Network optimization||16_lec.pdf 16_lec_ann.pdf|
|17||03/31||Interior point methods||17_lec.pdf 17_lec_ann.pdf||7 Out|
|18||04/05||Interior point methods II||18_lec.pdf 18_lec_ann.pdf|
|19||04/07||Linear optimization review||19_lec.pdf 19_lec_ann.pdf|
|20||04/14||Integer optimization||20_lec.pdf 20_lec_ann.pdf|
|21||04/19||Integer optimization algorithms||21_lec.pdf 21_lec_ann.pdf|
|22||04/21||The role of optimization||22_lec.pdf 22_lec_ann.pdf||8 Out|
|05/05||Final project out|
|05/07||Final project deadline|
There will be weekly 50 minutes long precepts. The focus will be on problem solving and Python programming. There are 3 available time slots:
- P01 (Rajiv Sambharya): Tuesdays 7:30pm - 8:20pm, Andlinger 017
- P02 (Irina Wang): Tuesdays 7:30pm - 8:20pm, Julis Romo A97
- P03 (Vinit Ranjan): Wednesdays 7:30pm - 8:20pm, Sherrerd Hall 001
The lecture notes are available from the course website and intended to be self contained. The following books are useful as reference texts. They are either free or digitally available via Princeton University library:
- [LO] D. Bertsimas, J. Tsitsiklis: Introduction to Linear Optimization (available Princeton Controlled Digital Lending)
- [LP] R. J. Vanderbei: Linear Programming: Foundations & Extensions (available on SpringerLink)
- [VMLS] S. Boyd, L. Vandenberghe: Introduction to Applied Linear Algebra – Vectors, Matrices, and Least Squares (available online)
In this course we strictly follow the crimes against matrices laws!
Precepts material and homework templates are available on the github companion repo.
- Linear algebra MAT202 and/or MAT204.
- Basic computer programming knowledge suggested.
Students will use the Python-based modeling software CVXPY (cvxpy.org) to solve optimization problems arising in several applications in operations research, finance, machine learning and engineering.
The assignments will be using jupyter notebooks. We suggest you edit them with Google Colab linked with your Google Drive (recommended way). Alternatively, you can run them locally by installing jupyter lab and the required packages on your machine. Please follow these instructions to complete the setup.
For a quickstart guide on how to use Python, have a look at this guide, especially sections on numpy, scipy and plotting with matplotlib.
All submissions should take place on Gradescope (accessible from the Canvas website).
25% Homeworks. 8 weekly homeworks. Almost all of them will include a computational component. Homeworks are due at Friday 9pm EST of following week. Requests for extension on homework will not be accepted, unless there is an extremely valid reason. Homeworks must always be submitted as a single pdf file which includes your written exercises (typed or handwritten) and code (pdf-exported jupyter notebook). You have three options to export your notebooks:
- On Colab: To export as pdf just click on: File → Print → Save as PDF. If this does not work or your some of your images are cut use the following
On Colab: To export as pdf run the following commands:
# Install required packages !apt-get install texlive texlive-xetex texlive-latex-extra pandoc cm-super dvipng !pip install pypandoc # Mount Google Drive from google.colab import drive drive.mount('/content/drive')
Then you can go to the notebook directory on your drive and export it, for example
%cd drive/MyDrive/orf307/homeworks/01_homework/ !jupyter nbconvert --to PDF "ORF307_HW1.ipynb"
- Local jupyter: To export as pdf just click on: File → Download as → PDF via LaTeX (.pdf).
- 40% Midterms. Two 120 minutes written exams. No coding required.
- 25% Final Project. 24 hours take-home final project with written and computational questions.
- 10% Participation. Students are expected to submit one question or note on each lecture on Ed Forum. The note should summarize what you learned in the last lecture, and highlight the concepts that were most confusing or that you would like to review. A note will receive full credit if: it is submitted before the beginning of next lecture, it is related to the content of the lecture, and it is understandable and coherent. You can make the note private (visible only by you and the course staff) or public, as you choose.
Students are encouraged to discuss and ask questions on Ed Forum. Please make sure to specify if questions are about General information of the course, about the Lectures or about Homeworks by assigning them to the related category.
- Homeworks. Students are allowed, and even encouraged, to collaborate on homeworks. When submitting your homework, you are required to list the name of the students you worked with. Also, please write the textbooks, notes or websites that were helpful to you.
- Midterms and final project. No collaborations allowed.
All work in this course must uphold the University’s commitment to academic integrity. This includes the Honor Code (for written examinations, tests, and quizzes) and guidelines for the submission of original work on all other assignments. More guidance can be found in Rights, Rules, and Responsibilities as well as the handbook Academic Integrity at Princeton.
Students are expected to attend each scheduled class on time and ready to participate fully. An excused absence will only be granted in the case of a religious observance, an ODS-approved accommodation, or -- as verified by your residential college -- a serious illness or an exceptional circumstance.