Optimization Modeling for Engineers
Northeastern University
Instructor: Laurent Lessard
This course provides an introduction to optimization modeling in engineering contexts. Topics covered include linear programming, quadratic and convex programs, and mixed-integer and non-convex models. By the end of the course, students will be equipped to transform practical engineering challenges into optimization models, assess their difficulty, solve them using modern software tools, interpret their solutions, and perform appropriate sensitivity and trade-off analyses. Examples will be drawn from all areas of engineering, as well as computer science and business/finance. Students should have taken a course on linear algebra (ME 2341 or equivalent) to register for this course.
IMPORTANT: The notes below are from Spring 2023-24, which was the last time Prof. Lessard taught this course. An older version of this course can be found here.
Part I: Linear programming
Lecture topic | Julia notebooks used in class | |
1. | Introduction Part I | Top Brass |
2. | Introduction Part II | Top Brass 2, Top Brass 3 |
Julia tutorial | Julia tutorial, JuMP tutorial, Plotting tutorial | |
3. | Linear programs | Standard Form |
4. | Minimax and planning | Chebyshev, House |
5. | Network flow problems | Sailco, Millco, Swim Relay |
6. | LP duality | Top Brass dual |
7. | Dual flows and algorithms | Solver diagnostics |
Part II: Convex programming
Lecture topic | Julia notebooks used in class | |
8. | Least squares | Regression |
9. | Equality constraints and tradeoffs | Moving Average, uy_data, Hovercraft |
10. | Regularization | Data Norm, Hover 1D |
11. | Quadratic forms and ellipsoids | none |
12. | QPs and QCQPs | Portfolio, folio_mean, folio_cov |
13. | Cones and semidefinite constraints | none |
14. | Convex programming | none |
15. | Duality | none |
16. | Review of convex optimization | none |
Class project and Q&A | none |
Part III: Nonconvex and combinatorial models
Lecture topic | Julia notebooks used in class | |
17. | Introduction to nonconvex models | Knapsack |
18. | Rounding and relaxation | none |
19. | Fixed costs and variable bounds | ClothCo, UFL |
20. | Logic constraints and integer variables | Sudoku |
21. | Set cover and TSP | CuttingPipe, TSP |
22. | Quadratic assignment and SOS | QAP, SOS |
23. | Cutting planes and branch & bound | none |
24. | Nonlinear programming | Tires, Polygon, Navigation |
25. | NLP algorithms | 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).- Installation guide (do this first!)
- Getting started (do this second!)
What is “optimization modeling”?
Optimization modeling is a process, and it starts with a description of a decision-making problem. All branches of engineering involve some form of decision-making! Here are a few examples:
- Design: Finding the best shape for a truss structure, ensuring structural integrity but also making it as light and inexpensive as possible.
- Supply chains: Finding the most efficient routes and schedules for shipping goods from multiple warehouses to various destinations, while minimizing transportation costs and meeting delivery deadlines.
- Manufacturing: Deciding the quantity of each product to produce in a factory to maximize profit, given constraints like production capacity, raw material availability, and market demand.
- Energy Usage in Buildings: Adjusting heating, ventilation, and air conditioning (HVAC) systems to minimize energy consumption while maintaining comfort levels in different zones of a building.
- Scheduling: Allocating staff in a hospital or customer service center to ensure adequate coverage at all times while minimizing labor costs and meeting service level agreements.
The final step is to solve the mathematical model using a computer and interpret the solutions. This will require some coding; you will learn to use a high-level modeling language and call open-source and commercial solvers to do the heavy lifting. This is not a coding class; we will not be implementing any algorithms ourselves, and no prior coding experience is needed. Nevertheless, we will learn the basics of different algorithms to understand their applications and what to expect when using them. Finally, we will learn to interpret the solutions and perform any relevant sensitivity analyses.
Target audience for the course
- Undergraduate students, generally seniors in ME, ECE, CEE, etc., who are graduating soon and realize they don’t know anything about optimization and want a “one-stop-shop” that will teach them how to recognize optimization problems in the wild and gain some basic literacy on the topic. The course has a project component, which would be an opportunity for students to include an optimization component in one of their large projects (e.g., Capstone/design).
- Graduate students that want to add breadth in optimization to complement their existing domain expertise. In the course project, these students could explore the use of optimization modeling for their current/ongoing research projects.
- Students considering IE/OR that are unsure where to begin and don’t really know/understand what is out there. This course can serve as a “gateway” course that provides enough breadth that students gain an idea of what interests them and where they can go from there.
- Students in Khoury (undergraduate or graduate) interested in optimization. CS courses tend to focus more on algorithms, so an optimization modeling course such as this one would complement existing algorithms courses nicely.
- If you are enrolled in an IE/OR program and are considering taking this course to complement the other optimization courses in your program, please consult your academic advisor.
What this class is not
- An algorithms class. We will briefly discuss the main classes of algorithms that modern solvers use so that you have a rough understanding of how different solvers work. Our discussions will cover the strengths and weaknesses of different algorithms (what sorts of guarantees do they provide? How efficient are they? How scalable are they?). Although we will be using state-of-the-art solvers in the class, we will not be coding/implementing any algorithms ourselves.
- A coding class. Optimization problems must generally be solved using a computer, so some amount of coding is inevitable… But this is not coding in the traditional sense. We will be using a “modeling language” that makes implementation relatively straightforward. No prior coding experience is needed.
- A machine learning class. Neural networks are generally viewed as a last resort in the context of engineering decision-making and planning problems, because they are computationally intensive and typically lead to uninterpretable solutions with few guarantees. That being said, machine learning problems can be framed as optimization models; learning about optimization can improve your understanding of machine learning. We will make these connections apparent in the class, as time permits. To learn about ML specifically, I suggest taking one of the many dedicated ML courses offered at Northeastern.
- A numerical methods class. Numerical methods are an important aspect of engineering analysis and design. Here, I’m using “numerical methods” to mean the solution of ordinary or partial differential equations over a spatiotemporal domain. The main examples are finite element analysis (FEA) and computational fluid dynamics (CFD). While FEA and CFD can be viewed as optimization problems, they are highly specialized and you should take a dedicated course on FEA or CFD to learn about these topics.
Topics covered in the course:
You should not know what most of the following keywords mean — if you do, this class is likely not for you!
- Linear programs. Geometrical interpretation, polytopes, assignment problems, minimax and planning problems, network flow problems, sensitivity analysis via LP duality.
- Quadratic programs. Least squares, minimum-norm, normal equations, equality constraints, trade-offs, quadratic forms, QCQPs, geometry of solutions.
- Conic programs. Cones, SOCPs, semidefinite programs.
- Convex programs. KKT conditions, sensitivity analysis via Lagrangian duality.
- Integer programs. Rounding and relaxation, fixed costs and variable bounds, logic constraints, set cover problem, traveling salesperson problem, quadratic assignment, special ordered sets.
- Nonlinear programs. nonlinear least squares, modeling techniques.
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 Spring 2024 (alphabetical by first author’s last name) — check them out!Authors | Project title | Files |
Guilherme Eymael | Aircraft geometry optimization | Notebook |
Turner Jennings | Weekly heartrate zone training optimization | Notebook |
Junning Jiao | Building the Singapore metro | Notebook, Data |
Immanuel Ampomah Mensah | Multi-agent pick-up and delivery | Notebook |
Darren Ng | WNBA travel schedule optimization | Notebook, Data |