Introduction to Optimization
University of Wisconsin–Madison
Instructor: Laurent Lessard
This course is an introduction to optimization from a modeling perspective. The aim is to teach students to recognize and solve optimization problems that arise in industry and research applications. Examples will be drawn from a variety of disciplines, including computer science, operations research, control and mechanical engineering, machine learning, and business/finance.
IMPORTANT: The notes and videos below are from Spring 2017-18, which was the last time Prof. Lessard taught this course. More recent offerings of the course might use different notes/materials. In particular, all code examples below were written for an older version of Julia and may no longer compile on the latest release!
Part I: Linear programming
Lecture topic | Video | Dates | Julia notebooks used in class | |
1. | Introduction Part I | Top Brass | ||
2. | Introduction Part II | Top Brass 2, Top Brass 3 | ||
Julia tutorial | Julia commands | |||
3. | Linear programs | video | Standard Form | |
4. | Minimax and planning | video | Chebyshev, House | |
5. | Network flow problems | video | Sailco, Millco, Swim Relay | |
6. | LP duality | video | Top Brass dual | |
7. | Dual flows and algorithms | video | none |
Part II: Convex programming
Lecture topic | Video | Dates | Julia notebooks used in class | |
8. | Least squares | video | Regression | |
9. | Equality constraints and tradeoffs | video | Moving Average, uy_data, Hovercraft | |
10. | Regularization | video | Data Norm, Hover 1D | |
11. | Quadratic forms and ellipsoids | video | none | |
12. | QPs and QCQPs | video | Portfolio, folio_mean, folio_cov | |
13. | Cones and semidefinite constraints | video | none | |
14. | Convex programming | video | none | |
15. | Duality | video | none | |
16. | Review of convex optimization | video | none | |
Class project and Q&A | video | Structural optimization |
Part III: Nonconvex and combinatorial models
Lecture topic | Video | Dates | Julia notebooks used in class | |
17. | Introduction to nonconvex models | video | Knapsack | |
18. | Rounding and relaxation | video | none | |
19. | Fixed costs and variable bounds | video | ClothCo, UFL | |
20. | Logic constraints and integer variables | video | Sudoku | |
21. | Set cover and TSP | video | CuttingPipe, TSP | |
22. | Quadratic assignment and SOS | video | QAP, SOS | |
23. | Cutting planes and branch & bound | video | none | |
24. | Nonlinear programming | video | Tires, Polygon, Navigation | |
25. | NLP algorithms | video | Iterative Methods |
Textbook:
There is no required textbook for the class. All course material will be presented in class and/or provided online as notes. That being said, there are several textbooks that cover parts of what we will see in class, and you may find it helpful to use them as references. Here are a few:- S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
The book is available for free here: http://stanford.edu/~boyd/cvxbook/. - H.P. Williams. Model Building in Mathematical Programming, 5th Edition. Wiley, 2013.
- R.L. Rardin. Optimization in Operations Research. Prentice Hall, 1998.
Coding:
You will be required to write code in Julia (http://julialang.org/), a programming language similar to Matlab and Python. We will also use the JuMP modeling language, which is a Julia module (Official JuMP documentation).- Download JuliaPro. It comes bundled with the IJulia notebook and several popular packages, including JuMP.
- Alternatively, you may run Julia in your browser using JuliaBox. Simply log in with any Google account and create a new file using “Julia 0.6.2”. This method will get you started instantly but is perhaps less reliable in the long run.
- Noteworthy differences from other languages.
- Another cheatsheet comparing Julia syntax to other languages.
- Learn X in Y minutes Julia tutorial.
- Official Julia documentation.
- A handy cheat-sheet.
- IJulia documentation
- Markdown cheatsheet
- Equations formatted using $…$ in LaTeX.
- Another reference sheet for LaTeX can be found here.
Official syllabus:
The official syllabus for the class is available here.Important dates:
- Tue Jan 23: first lecture
- Thu Mar 22: midterm exam (7:15–9:15pm, Ingraham Hall B10)
- Tue Mar 27 and Thu Mar 29: spring break (no classes)
- Fri Apr 6: project proposal is due
- Thu May 3: last lecture
- Mon May 7: final project report is due
- Other important dates: https://registrar.wisc.edu/spring_deadlines_at_a_glance.htm
Grading:
There will be three main components to your grade:- Homework: 45%. There are weekly (roughly) homework assignments (8-10 total). These will be graded on a coarse 4-point scale. You get 4 points if you attempted all problems and got everything mostly right.
- Midterm exam: 25%. There will be an exam before spring break where you will be tested on all the material covered up to that point. The exam will be taken outside of regular class hours (see date and time above) so be sure that you have no scheduling conflicts. It is your responsibility to ensure that you are available and present for the midterm exam.
- Project: 30%. There will be a group project due at the end of the semester. More information here.
More information about homework assignments
- Homework assignments are due Sunday by 11pm. They can be turned in up to two days late at a penalty of -25% per day. Solutions will be posted to the class website on Wednesday.
- Exceptions will be made to the rules above in order to accommodate special circumstances. This includes family or medical emergencies, religious observances, and documented disabilities. If you have a special circumstance and foresee a conflict, please email the instructor as soon as possible to make alternative arrangements.
- Assignments must be turned in electronically (as PDF or images) via gradescope. For a tutorial on how to do this, please watch this video. If you’ll be scanning documents in using a camera phone, read this guide.
- Problems requiring code must be solved using an IJulia notebook. You must turn in a PDF version of your notebook. Do not turn in raw code such as an
.ipynb
or.jl
file. The easiest way to turn a notebook into PDF is to use your browser’s “print to PDF” function. Be sure to compile your file (so we can see the outputs) before you turn it in. - For problems not requiring code, you may write up solutions by hand or electronically (e.g. using Word, LaTeX, or an IJulia notebook). Either way, you must turn it in electronically.
- Start each problem on a new page if possible. At the very least, be sure that each new problem is clearly indicated (use a large heading in Markdown to indicate each new problem, for example). If a problem has multiple parts, it’s OK to answer them on a single page.
- Start early. You have two weeks (three weekends) to complete assignments, so you can expect them to take longer than standard one-week problem sets. They are also worth a significant portion of your final grade. You have plenty of opportunities to get help during office hours or via Piazza, so the earlier you get started, the better!
- Explain your work. This means write in words how you solved the problem, use intuitive variable names, and comment any code you turn in. It is unacceptable to simply turn in undocumented code. Even if your code produces the correct result, you will likely lose points.
- You are encouraged to discuss homework problems with classmates and even work in groups. However, the work you turn in must be your own. If you use any external sources (e.g. the internet) be sure to cite your sources!
The goal of the class project is to explain, model, and solve an optimization problem using techniques we learned in class. It’s an opportunity to pursue that idea you’ve been thinking about for some time but didn’t know how to best approach it! Some students also bring in problems related their own graduate or undergraduate research.
Here are some of the top projects from the Spring 2018 semester (alphabetical by first author) — check them out!
Authors | Project title | Files |
Om Bathija | Pay Me Maybe: Settle Group Bills | Notebook, Data |
Katie Biegel and Alex Tanke | Going for Baroque: Scheduling an Artistically Meritorious and Financially Feasible Symphony Orchestra Season | Notebook, Data |
Alex Dawson-Elli, Patrick Dills, and Kieran Nichols | Trajectory Optimization using Direct Collocation | Notebook, Data |
Jacob Johnson | Strategic Amortization of Multiple Student Loans | Notebook, Data |
John Sandgren, Benjamin Morris, Abigail Purfuerst, and Casey Kong | National Park Optimization | Notebook, Data |
Jay Wang | CS 506 Group Assignment Optimization | Notebook, Data |
Here are some of the top projects from the Spring 2017 semester:
Authors | Project title | Files |
Ian Atkins | Indoor Farm HVAC Optimization | Notebook, Data |
Tuan Dinh and Varun Sah | Determining Winning Strategies Using Game Theoretic Optimization | Notebook, Data |
Bailey Flanigan and Andrew Duplissis | Optimizing the WIMR Elevators | Notebook, Data |
Yash Govind and Hakan Memisoglu | Optimizing Scheduling for Dataflow program | Notebook, Data |
Alex Haufler and Patrick Forbes | Optimally Uniform Magnetic Fields Using Discrete Circular Electromagnetic Coils | Notebook, Data |
Yiqiu Zhang and Jia Zhuang | Forest Harvest Company Distribution Optimization | Notebook, Data |
Here are some of the top projects from the Spring 2016 semester:
Authors | Project title | Files |
Aritra Biswas and Prathusha K. Sarma | Wanderlust: Optimizing Group Travel Plans | Notebook, Data |
Wayne Chew and Sahit Mandala | Fiber Optic Network Topology Optimization | Notebook, Data |
Christopher E. Lawson, Lise O. Aagesen, and Eric C. McCurry | Dynamic Metabolic Modelling of Nitrifying Consortia | Notebook, Data |
AJ Nosek and Newton Wolfe | Minimizing Economic and Public Health Impacts of Radioactive Contamination | Notebook, Data |
Nate Pritzl and Logan Colla | Fantasy Football Roster Optimization | Notebook, Data |
Peter Schlafly and Sam Olson | Selecting the Best Possible NHL Expansion Team | Notebook, Data |
Michael Scott and Drew Patenaude | Optimization of Trajectories through Dynamical Gravitational Systems | Notebook, Data |
Ananth Sridhar, Rangapriya Parthasarathy, and Song Mei | Image Mosaicking | Notebook, Data |
Jennifer Witt | Optimizing Telescope Time | Notebook, Data |
Haojun Zhang and Keyi Cui | Using Optimization for Task Scheduling | Notebook, Data |