Syllabus

Subject Description and Goals

15.053 is an undergraduate subject in the theory and practice of optimization. We will consider optimization models with applications to transportation, logistics, manufacturing, computer science, E-business, project management, finance as well as several other domains. This subject will survey some of the applications of optimization, and we will present algorithms and theory for linear programming, network flows, dynamic programming, integer programming, and decision trees.

One way of summarizing a subject is a lecture by lecture description of the subject, or a description of the methodologies presented in the subject. We do list a lecture by lecture description, but first we describe several cross-cutting themes.

Themes for 15.053

1. Optimization is Everywhere
   
   We will present applications of optimization to a wide range of fields including operations management, finance, marketing, engineering, and strategic planning, as well as operations of a university and personal decision making. We will also present different models and conceptual frameworks for optimization including linear programming, integer programming, non-linear programming, decision trees, and dynamic programming.
   
   
2. Algorithms
   
   As is traditional at MIT, we learn the inner workings of algorithms. It is not sufficient to say that Excel contains an algorithm that solves linear programs. We need to know how the algorithm works. Learning algorithms has several important implications. First of all, some problems are easily solved, and others are intrinsically intractable. Learning the algorithms helps to distinguish one from the other and provides insight into where the computational difficulties arise. Second, understanding the behavior of an algorithm can be an important first step in interpreting the output of the algorithm and applying it to gain insight about the optimization problem. Third, it is only by understanding the inner working of algorithms that we are in a position to design our own algorithms, or modify those that exist.
   
   
3. The Goal of the Models is Insight, Not Numbers
   
   We build models not as a mirror of reality, but only as a partial reflection of reality. The nature of modeling in Management Science and Operations Research is that we approximate reality in order to provide support for decision making. One useful way that models support decision making is that they permit managers to explore a range of scenarios in order to help in determining which decisions are robust under a number of assumptions. In a similar manner, one can analyze models to determine which numbers are the most important, and which numbers can be changed with little impact on the decision. A major theoretical tool for aiding insight is sensitivity analysis and its variations. One caveat is that in many E-business applications, one needs to solve thousands of models over a short period of time. In this case, there is not time for human assessment of model outputs, and we need to design models that are robust and trustworthy.
   
   
4. Performance Guarantees
   
   One of the hallmarks of optimization (and mathematical programming) is that it provides both an optimal solution, and also provides a succinct certificate (guarantee) of optimality. Even when a problem is intrinsically difficult, optimization-based techniques may provide some guarantees. A particularly useful guarantee is a maximum relative distance from optimality.

Required Text

The required text for this subject is Winston, Wayne. Operations Research: Applications and Algorithms. Boston, MA: Duxbury Press, 1994. ISBN: 0534209718.

(The following book has all the materials needed for the subject except for material on decision analysis. You may be able to obtain used copies of this book more cheaply: Winston, Wayne and Munirpallam Venkataraman. Introduction to Mathematical Programming - Applications and Algorithms. Boston, MA: Duxbury Press, 2002. ISBN: 0534359647.)

Additional materials including course notes and readings and spreadsheets will be made available. All of the spreadsheets require Excel, and many of the spreadsheets require Excel Solver.

Midterms, Recitations, Quizzes, Grading, and Challenge Problems

There will be two midterm exams. The second midterm covers material subsequent to that covered on the first midterm. The final exam covers decision trees, dynamic programming, and models for LP and IP. It is not a comprehensive exam. The midterms and final exam are closed book.

Friday recitations are required. During most Friday recitations, there will be a 10 minute quiz that is worth 2% of the final grade. The quiz will include questions on very elementary material presented during that week, as well as an elementary exercise or two related to the previous week's homework set. It will be designed so that those who attended class (or are familiar with the contents) and who are familiar with the previous weeks homework set should do very well.

Grading

Evaluations will be based upon the following components weighted by the given percentages.

There will be weekly problem sets, each of which will consist of around 6 to 8 problems.

Each of the 10 assignments will be graded out of 2.5 points.

Each homework will first be graded out of x points, where x depends on the homework set and then converted to a 2.5 point scale. The conversion is roughly as follows.

The homework grades are incorporated in a manner to achieve the following two goals:

1. Provide incentives for students to do a good job in homework exercises, and
   
   
2. Permit students to receive help with homework, but not provide an incentive for receiving "too much help."

In particular, we do not want to penalize students who prefer to work independently.

Homework should be handed in (hard copy) and should not be submitted electronically.

Students should take into account that not handing in any homework assignment is tantamount to losing 62.5 points on each of the midterms. Not taking any of the recitation quizzes is tantamount to losing 40 points on each of the midterms.

The graders and/or TAs will grade all problems. In addition, solutions will be provided for each of the problems.

Challenge Problems

Each homework set will have one or two challenge problems. These problems are optional, but will count towards your raw grade on the homework. However, they are not necessary for obtaining 2.5 points (the maximum score), as per the grading scheme above. The challenge problems are recommended for those students who want to concentrate in Operations Research or who want to obtain a deeper knowledge of the material. In addition, at the end of the semester, the progress in challenge problems may help those students on a grade boundary, and will be used in helping to determine which students obtain an A+ in the class.

Extra Credit

During the semester, students are eligible for obtaining up to 5 points extra credit by doing a small project. The extra credit can be arranged with the TAs. Some suggested extra credit projects include the following:

1. Make a Short Video
   
   (Can be done in teams of 2 to 4 students.) Making one or two videos that are each from 60 seconds to 2 minutes in length. We would refer to these as "Optimization in 60 seconds." Each video would be something that students in 15.053 would find engaging and a learning experience. It could illustrate applications of OR or could illustrate an important technical point. (Humor is encouraged, but not so much that we would be embarrassed to show it to future classes.) The video should be set up on your own website in such a way that it can be streamed from other websites.
   
   
2. Create Homework Problems
   
   (Can be done individually or in a group of 2 students). Creating from 3 to 5 homework problems that are engaging for students and would be appropriate for homework for future classes, possibly including challenge problems or spreadsheet based exercises.
   
   
3. Creative Project Design
   
   (2 to 4 students.) Determine an interesting way that Optimization could be used in a practical situation, and lay out how you think it could be used. Give the background on the problem. Determine what data would need to be collected, what you believe the constraints are, and what would need to be optimized. Try to keep to a maximum of 3 typed pages.

Late Homework Policy

Assignments are due at the beginning of the class on the day that they are assigned. They may be handed in at the classroom, or they may be submitted electronically to the TA, or they may be handed in to Professor Orlin's secretary. Late assignments will not be accepted. However, one assignment may be handed in up to 24 hours late during the semester, along with a very brief excuse why it is late.

Policy on Individual vs. Joint Work

Students may work in pairs if they choose, and may submit a joint write-up of homework. Students should not share written answers (except for sharing with one's partner), and it is not permitted for one student to copy (or nearly copy) the answer of someone else nor the answer of a homework solution from a previous semester. Copying solutions from existing materials or from other students will result in no credit for the homework assignment.