Projects
- Introduction (PDF)
- Formulations of linear and non-linear programs (PDF)
- Geometry and visualizations of linear programs (PDF)
- The simplex method 1 (PDF)
- The simplex method 2 (PDF)
- Sensitivity analysis and shadow prices (PDF)
- Game theory 1: 2-person 0-sum, or constant sum (PDF)
- Game theory 2 (PDF)
- Discussion of projects; slack variables vs. artificial variables (PDF)
- Introduction to integer programming (PDF)
- Integer programming formulations (PDF)
- Integer programming techniques 1: branch and bound (PDF)
- Integer programming techniques 2: cutting planes (PDF)
- Integer programming formulations, again (PDF)
- Networks 1: Shortest path problem (PDF)
- Networks 2: Network flows (PDF - 1.4MB)
- Networks 3: Traveling salesman problem (PDF)
- Decision trees 1 (PDF)
- Decision trees 2: the value of information (PDF)
- Behavioral economics (PDF)
- Recitation 1 problems (PDF)
- Recitation 1 solutions (PDF)
- Recitation 2 problems (PDF)
- Recitation 2 solutions (PDF)
- Recitation 3 problems (PDF)
- Recitation 3 solutions (PDF)
- Recitation 4 problems (PDF)
- Recitation 4 solutions (PDF)
- Recitation 5 problems (PDF)
- Recitation 5 solutions (PDF)
- Recitation 6 problems (PDF)
- Recitation 6 solutions (PDF)
- Recitation 7 problems (PDF)
- Recitation 7 solutions (PDF)
- Recitation 8 problems
- Recitation 8 solutions (PDF)
- Recitation 9 problems (PDF)
- Recitation 9 solutions (PDF)
- Recitation 10 problems (PDF)
- Recitation 10 solutions (PDF)
- Problem Set 1 – Group 1 (PDF)
- Problem Set 1 solutions – Group 1 (PDF)
- Problem Set 2 – Group 1 (PDF)
- Problem Set 2 solutions – Group 1 (PDF)
- Problem Set 3 (PDF)
- Problem Set 4 (PDF)
- Problem Set 4 solutions (PDF)
- Problem Set 5 (PDF)
- Problem Set 5 solutions (PDF)
- Problem Set 6 (PDF)
- Problem Set 6 solutions (PDF)
Background
15.053 aims to teach students methods for identifying and solving optimization problems. In order to bring these concepts to life, students will be preparing group projects to identify and model a real world optimization problem. The student teams will select an actual situation and use the concepts from class to define the problem, build an optimization model, and solve it.
Teams should first brainstorm situations from their personal experiences that could benefit from optimization. These can include a problem that can be fully solved; that is, the data is available and the solution techniques are also available. Or they can involve more complex problems in which students focus on what they would do if they could solve the full problem. (Even in the latter case, students should collect some data and carry out some optimization for some aspect of their problem.)
Groups should define the problem that they wish to solve using the concepts learned in class. Students must also conduct research to collect data that can be used to model the problem and eventually solve it (using surveys, data sources, focus groups, etc.). Successful projects will include a variety of techniques learned in class (e.g., modeling, Solver, sensitivity analysis). They may also involve knowledge or techniques from other classes (e.g., data analysis). The project should include a qualitative assessment of the situation and a quantitative component that can actually be solved. Students can also detail "next steps" or what they would do next to solve the problem.
Objectives
- Identify practical applications for concepts learned in class
- Conduct analysis while leveraging course material
- Learn about assorted real-life situations where optimization methods can be used
- Utilize a different approach for learning and mastering 15.053 concepts
- Learn about applying optimization in practice, including learning the difficulties that may be associated with finding the right data and forming a useful model
Team Structure
Student teams will consist of three or four persons each. Students may select their team members or they can be assigned by the course TAs.
Teams of two students may be allowed in rare circumstances. The TAs will randomly assign a third member to teams of with only two members, and we will also assign a fourth member if the team prefers.
Students should submit the list of members of their team to the TAs. (See list of deadlines below.) The TAs will form groups for students not already on a team and will add students to teams of two. Team members may divide up certain aspects of the project, but it must be a group effort and include contributions from every member.
DUE DATES | DELIVERABLES |
---|---|
One day before Lec 10 | Members of team. Send members of your team to the TAs via email, if you wish to form your own team. |
Lec 10 | TAs will assign students not already in teams. |
Two days after Lec 11 | Topic of project, and a very brief description. Send this information to the TAs. This should be a one paragraph description of the project. If desired teams can present descriptions of two different projects. In this case, the TAs will provide feedback to the teams on the possible merits of the two proposals. |
Lec 13 | Draft of project proposal. Teams should submit a 1 page proposal giving a brief description of the project being modeled. The proposal should describe the solution technique that will be used (or will be developed) as well as the data to be collected. |
Midterm exam 2 (between lectures 15 and 16) | Final project proposal. Students should submit a revision of the draft due at Lecture 13, taking into account what they have learned in the past two weeks. |
Lecture 17 | Students will vote on which class projects they would like to see presented in the last two class sessions. The remaining teams will make oral presentations outside of class (see below). |
Lecture 20 |
There are two written deliverables for the final project. Final team paper. This 4 to 6 page paper should include a more detailed description of the goals of the project and what was accomplished. It can also include comments on efforts that did not produce the intended results. It should conclude with ways in which the project could have been enhanced if there were more time and if data were more easily available. The write-up may include charts, small tables, and graphs. Large tables, copies of any spreadsheets, and any other model analysis may be included as desired, but as an appendix (not part of the 4 to 6 pages). Write-up on individual leanings. In addition to the team project, each team member should submit a separate one-page description of one or two mistakes that you learned from when carrying out the project. Ideally, the mistake(s) that you learned from should have longer-term implications for yourself (e.g., learning about how to write a useful model, or what kind of data is useful, or what kind of data is available, or how hard it is to develop a new solution technique, or the time it takes to accomplish certain types of tasks). |
Lectures 22–23 | Team presentations. Teams that are not presenting during Lectures 22–23 should select a 15 minute time slot in which they will make a team presentation. The remaining teams will be able to sign up for time slots outside of class hours for their 10–15 minutes presentations. Sign up for time slots will take place the preceding week. The PowerPoint presentations should involve all team members. (Other presentation software may be used instead of PowerPoint.) |
Grading
This assignment will be worth 20% of the final grade for the course. It will take into account (1) what was proposed and accomplished, (2) what was learned (especially when efforts were made that did not have the intended results), (3) ideas on how to make the project better, (4) and the quality of the written and oral presentations.
Staff and Consulting Support
One of the TAs or Professor Orlin will meet at least twice with each student team during the course of the projects. In addition, the staff is available to answer questions relating to the project throughout April and early May.
In addition, there are five doctoral students in the OR Center who have volunteered several hours a week in April and May to serve as "consultants." They can provide feedback on what you have proposed to do, and may offer suggestions that either simplify your task or enhance your ability to achieve your goals. (They are not available for suggesting projects.) If you are interested in meeting with one of the consultants for up to ½ hour per week, please contact one of the TAs.
Limits to Excel Solver and Alternatives
Solver is limited to 200 decision variables for all models, and it is limited to 100 constraints for nonlinear models. While many successful projects will be possible with these limits, other projects will need software capable of solving much larger optimization problems. There are also tools that permit upfront programming or scripting to formulate the model. The TAs and consultants will provide limited support to groups wishing to learn and use other tools (such as CPLEX, AMPL^{®}, OpenSolver, YALMIP in MATLAB™, open source solvers in common programming languages, etc).
Sample Topics
- School bus scheduling
- Optimization in radiation therapy
- Exam scheduling at MIT or elsewhere
- Assigning K-12 students to public schools
- Portfolio optimization
- Scheduling residents in hospitals
- Optimal location of cell phone towers
- Meal selection (and diet) problems
- Optimal strategies for sports teams
- Optimal allocation of wind turbines
- Optimal pricing problems
- Optimal inventory control
- Optimal truck routing