Introduction to Optimization
University of Wisconsin–Madison
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.
Lectures: Tue/Thu, 1:00pm–2:15pm, CompSci, Room 1221.
Instructor: Laurent Lessard.
Office hours: TBA, usually Mon/Fri, 11am-12:30pm, Discovery bldg.
(near Aldo’s cafe). Also, in class before+after lecture.
Discussion forum: Piazza.
Submitting assignments: Gradescope.
Note: Only the rows containing a date are guaranteed to be current. All other rows contain notes and code from last year’s class (for your reference). Topics covered this year may change at my discretion. Also, code from last year may not compile properly as Julia and JuMP have undergone significant changes in the past year.
Part I: Linear programming
Lecture topic | Dates | Julia notebooks used in class | |
1. | Introduction Part I | Jan 17 | Top Brass |
2. | Introduction Part II | Jan 19 | Top Brass 2, Top Brass 3 |
3. | Linear programs | Jan 26 | Standard Form |
4. | Minimax and planning | Jan 31 | Chebyshev, House |
5. | Network flow problems | Feb 2 | Sailco, Millco, Swim Relay |
6. | LP duality | Feb 7 | Top Brass dual |
7. | Dual flows and algorithms | Feb 9 | none |
Part II: Convex programming
Lecture topic | Dates | Julia notebooks used in class | |
8. | Least squares | Feb 14 | Regression |
9. | Equality constraints and tradeoffs | Feb 16 | Moving Average, uy_data, Hovercraft |
10. | Regularization | Feb 21 | Data Norm, Hover 1D |
11. | Quadratic forms and QPs | Feb 23, Feb 28 | Portfolio, folio_mean, folio_cov |
12. | Cones and semidefinite constraints | Feb 28, Mar 2 | none |
13. | Convex programming | Mar 7 | none |
14. | Duality | Mar 9, Mar 14 | none |
15. | Review of convex optimization | Mar 14 | none |
Part III: Nonconvex and combinatorial models
Lecture topic | Dates | Julia notebooks used in class | |
16. | Introduction to nonconvex models | Mar 28 | Structural optimization |
17. | Rounding and relaxation | Mar 30 | none |
18. | Fixed costs and variable bounds | Apr 4 | ClothCo, UFL |
19. | Logic constraints and integer variables | Apr 6 | Sudoku |
20. | Set cover and TSP | Apr 11, Apr 13 | CuttingPipe, TSP |
21. | Quadratic assignment and SOS | Apr 13 | QAP, SOS |
22. | Cutting planes and branch & bound | Apr 18 | none |
23. | Nonlinear programming | Apr 25 | Tires, Polygon, Navigation |
24. | NLP algorithms | Apr 27 | Iterative Methods |
Discussion forum:
We will use Piazza (https://piazza.com/wisc/spring2017/cseceisye524/home) for class-related discussions. Do not email the course staff directly with questions. Use Piazza or attend office hours!- On Piazza, anybody can ask questions, answer questions, or edit/improve existing responses. If you’re struggling with a concept, chances are you’re not alone—by posting your question on Piazza, it helps everybody!
- Do not use Piazza to ask for solutions, do not post solutions, and be nice to each other!
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).- Follow this installation guide to get you up and running with Julia/IJulia/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.5.0”. 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.
Important dates:
- Tue Jan 17: first lecture
- Thu Mar 16: exam (7:15-9:15pm, 113 Psychology)
- Tue Mar 21 and Thu Mar 23: spring break (no classes)
- Mon Apr 3: project proposal is due
- Thu May 4: last lecture
- Mon May 8: final project report is due
- Other important dates: https://registrar.wisc.edu/spring_deadlines_at_a_glance.htm
Course syllabus:
Week 1 | Jan 17 and 19 | Introduction, optimization models, solvers, examples |
Week 2 | Jan 24 and 26 | Julia tutorial, geometry of linear programs (LP), standard form |
Week 3 | Jan 31 and Feb 2 | LP: minimax, planning, transportation, assignment, and network flow problems |
Week 4 | Feb 7 and 9 | LP: duality, sensitivity, complementary slackness, algorithms |
Week 5 | Feb 14 and 16 | Least squares, equality constraints, regression, trade offs |
Week 6 | Feb 21 and 23 | Regularization, norm choice, quadratic forms, QPs |
Week 7 | Feb 28 and Mar 2 | Cone constraints, SOCPs, SDPs, Robust LPs |
Week 8 | Mar 7 and 9 | Convex programming, general duality |
Week 9 | Mar 14 and 16 | Loose ends and review for the exam |
Week 10 | Mar 21 and 23 | Spring break (no class) |
Week 11 | Mar 28 and 30 | Nonconvex models, hardness, relaxations |
Week 12 | Apr 4 and 6 | Mixed-integer programs (MIP), generalized assignment |
Week 13 | Apr 11 and 13 | Logic constraints, traveling salesman |
Week 14 | Apr 18 and 20 | QAP, SOS constraints, algorithms |
Week 15 | Apr 25 and 27 | Nonlinear programming (NLP): models, examples, algorithms |
Week 16 | May 2 and 4 | Reserved for working on the class project |
Grading:
There will be three main components to your grade:- Homework: 45%. There are weekly (roughly) homework assignments (8-10 total).
- 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, so be sure that you have no scheduling conflicts.
- Project: 30%. There will be a group project due at the end of the semester. More information here.
Important information:
- Homework assignments are due Monday. They can be turned in up to two days late at a penalty of -25% per day.
- It is your responsibility to ensure that you are available and present for the exam. The date and time are set, so plan accordingly!
- 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.
- 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!
Instructions for submitting homework
- All homework assignments are due by 11:00pm on the date indicated.
- 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. - Start each problem on a new page. If a problem has many parts, it’s OK to answer them on a single page.
- 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.
Additional guidelines and rules
- 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!
Basic information
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.
You will work in small groups for the project and produce a final report in the form of an IJulia notebook. Here are some of the top projects from the Spring 2016 semester (alphabetical by first author) — check them out!
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 |
Project proposal (due Monday April 3)
- Fill in the following form: Project proposal (also in MS Word format)
- Upload the completed form to Gradescope. Be sure to upload only one form per group. You’ll have the option to select your group members within Gradescope once you upload.
- There is no restriction on topic choice. A list of suggested topics is provided below but you are encouraged to come up with your own topics.
- Your proposal will be checked to make sure your project idea sounds reasonable. You’ll receive feedback about your proposal within a week. There will be no grade associated with the proposal.
Final report (due Monday May 8)
The report, which you will submit as a group, will be an IJulia notebook. Use the following file as a template. You will not be submitting a PDF this time; you will be submitting the .ipynb file for your notebook. More details to come later! The report should contain the following sections:- Introduction (15%): The first few sentences should give a quick overview of the entire project. Then, elaborate with a description of the problem that will be solved, a brief history (with citations) of how the problem came about, why it’s important/interesting, and any other interesting facts you’d like to talk about. You should address and explain where the problem data is coming from (research? the internet? synthetically generated?) Also give an outline of the rest of the report. This section should be 300-600 words long and accessible to a student that has not taken the course.
- Mathematical model (20%): A discussion of the modeling assumptions made in the problem (e.g. is it from physics? economics? something else?). Explain the decision variables, the constraints, and the objective function. Finally, show the optimization problem written in standard form. Discuss the model type (LP, QP, MIP, etc.). Equations should be formatted in LaTeX within the IJulia notebook. This section should be accessible to a student that has taken the course
- Solution (25%): Here, you should code up your model in Julia + JuMP and solve it. Your code should be clean, easy to read, well annotated and commented, and it should compile! You are not allowed to use other programming languages or DCP packages such as convex.jl. I will be running your code. I suggest having multiple code blocks separated by text blocks that explain the various parts of your solution. You may also solve several versions of your problem with different models/assumptions.
- Results and discussion (25%): Here, you display and discuss the results. Show figures, plots, images, trade-off curves, or whatever else you can think of to best illustrate your results. The discussion should explain what the results mean, and how to interpret them. You should also explain the limitations of your approach/model and how sensitive your results are to the assumptions you made.
- Conclusion (5%): Summarize your findings and your results, and talk about at least one possible future direction; something that might be interesting to pursue as a follow-up to your project. Be specific enough with your follow-up idea to show that you have given it some thought and that you think it’s actually doable!
Suggested topics
Keep in mind these are only suggestions! You are encouraged to come up with your own ideas and to draw inspiration from your work, your research, your other classes, your everyday life, or your imagination!- Examples from class or homework may be used as starting points provided you expand the topic significantly. Ideas:
- Planning problems (cf. house building example). What if we have a limited number of workers? What if certain equipment is required for certain tasks and that equipment has limited availability? What if certain tasks cannot be worked on simultaneously?
- Scheduling meetings (cf. doodle problem). What if we had to schedule multiple people on the same day? What if only certain subsets of people needed to meet with certain visitors? What if different people had different meeting duration requirements?
- Vehicle control (cf. hovercraft problems). Investigate vehicles with more complicated dynamics such as a car or bicycle. These vehicles have non-holonomic constraints (direction they can move in depends on which way they’re pointing), and they also have turning radius constraints. Optimal way to parallel-park a car?
- Portfolio optimization (cf. portfolio problem from class). The example seen in class is a very basic version using a simple mean-variance tradeoff. What about more complicated models of risk?
- Examples covered in classes at other schools may also be used as starting points. Always cite your sources! Ideas:
- Examples from EE364a at Stanford: examples
- Examples from EE236a at UCLA: structural optimization or control applications.
- Examples from convexity short course. These examples already contain code (Python + cvxpy). If you choose one of these ideas, you must write your own Julia + JuMP code and you cannot simply duplicate the provided examples!
- Examples from EE127a at Berkeley: website. Take a look at the case studies.
- Problems with integer variables. We will start looking at this topic after spring break and we will cover many examples that might serve as starting points for class projects.