15.053.    Optimization Models in Management Science
                    General Information

                            Spring 2006

Subject website:  http://sloanspace.mit.edu/

For the Powerpoint Overview of 15.053, as presented by the MIT Beaver, click below.
http://web.mit.edu/jorlin/www/15.053/15053_Overview_2006.ppt

Tuesdays, Thursdays, 10 to 11:30 in E51-335

Tuesdays, Thursdays, 2:30 to 4 in E51-345

Recitations.  All recitations are on Friday and last one hour.  Recitations have required attendance.  Students will be assigned a recitation during their first week, based on stated preferences.

Midterm Exams.  There will be midterm exams on the evenings of March 15th and April 20th.  Please be sure to put them on your calendar to avoid conflicts.

Professor

James Orlin

Office

E40-147

Phone

x3-6606

e-mail

jorlin@mit.edu

Teaching Assistants

Doug Fearing
Mike Metzger               
Karima Nigmatulina              

TOPICS

 

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, 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, and decision trees.
  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 varying 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.

Required Text and On-Line Tutorials

The required text for this subject is Operations Research:  Applications and Algorithms (4th Edition) by Wayne Winston.

There will also be several on-line tutorials that are required for class.  In some cases, the reading is required prior to the class presentation.

In addition, there is a recommended textbook Applied Mathematical Programming, by Bradley, Hax and Magnanti (Addison-Wesley, 1977). This textbook is out of print, and is available at http://web.mit.edu/15.053/www
up

 

15.053   Course Outline                                 

 

Date

Topic

Readings

1

 Feb. 7

Introduction to Linear Programming and Operations Research

Sections 1.1 to 1.5 
Sections 3.1  and  3.3 to 3.6

2

 Feb. 9

Applications of Linear and Non-Linear Programming

Sections 3.7 to 3.12

3

 Feb. 14

Geometry of Linear Programming

Sections 3.2 and 5.1

4

 Feb. 16

Simplex Method 1

Sections 4.1 to 4.5

5

 Feb. 23

Simplex Method 2

Sections 4.6 to 4.8, 4.11, 4.12 and 4.17

6

 Feb. 28

Sensitivity Analysis

Chapter 5

7

 March 2

Linear Programming Duality 1

Sections 6.5 to 6.9

8

 March 7

Linear Programming Duality 2

 

9

 March 9

Success Stories of Linear Programming

 

10

 March 14

 

 

March 15

No class.  Review session from 7:30 to 9:30 PM

 
Midterm 1:  7:30 to 9:30 PM.

 

11

 March 16

Game Theory 1:  2-Person 0-sum game theory

Sections 14.1 to 14.4

12

 March 21

Game Theory 2:  Cooperative Game Theory

Sections 14.5 to 14.7

13

 March 23

Introduction to Networks

Sections 8.1 to 8.2 plus class handout

14

 April 4

Networks 2.   Maximum Flows.

Section 8.3 plus class handout

15

 April 6

Networks 3.  Min Cost Flows Plus More

Section 8.4 plus class handout

16

 April 11

Networks 4:  The Network Simplex Algorithm

Handout to be provided

17

 April 13

Success Stories of Network Optimization

 

18

April 19

 

 

April 20

Review session from 7:30 to 9:30 PM

 

No class.

Midterm 2 from 7:30 to 9:30 PM

 

19

 April 25

Integer Programming Models

Sections 9.1 and 9.2

20

April 27

More Integer Programming Models

 

21

 May 2

Solving Integer Programs I : Branch and Bound

Sections 9.3 and 9.5 to 9.7

22

 May 4

Solving Integer Programs II: Cutting Planes

Section 9.8

23

 May 9

Success Stories of Integer Programming

 

24

 May 11

Decision Trees 1

Sections 13.1 to 13.4

25

 May 16

Decision Trees 2.  Value of information.  Sensitivity analysis.

Section 13.5

26

Thursday May 18

Last Lecture

 

up

Midterms, Recitations, Quizzes, Grading, and Challenge Problems

The two midterms will be on the evenings of March 15 and April 20 from 7:30 to 9:30 PM. 

The first midterm covers the content of Lectures 1 to 9.  -- “Content” includes tutorials plus any additional material covered on problem sets. --   The second midterm covers the content of lectures 11 to 17.  The “final exam” covers the covers the content of lectures 19 to 25.  The midterms and exam are all closed book.

Friday recitations are required.   During most Friday recitations, there will be a 10 minute quiz that is worth 2.5% of the final grade.  In addition, the lowest two quiz grades will be dropped.  The quiz will include questions related to the homework set due immediately prior to the recitation, except for first quiz, which will be very elementary, and the quiz on April 28th, which will have elementary questions on integer programming.  It will be designed so that those who understood the homework set should do very well.

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

 

Homework

20 %   (2.5% each)

Weekly Quizzes

20%    (2.5% each)

Midterm 1

20 %

Midterm 2

20 %

Exam

20 %

 

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

Each of the 9 problem sets will be graded out of 2.5 points.  The problem set with the lowest assigned grade will be dropped.  Each of the 10 quizzes will be graded out of 2.5 points.  The lowest two grades will be dropped.

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. 
 

Homework Grade

Interpretation

2.5

85% to 100%

2

75% to 84% 

1.5

60% to 74%

1

50% to 59%

0

49% or less

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 each homework assignment is comparable in value to 12.5 points on a midterm.  Not handing in homework sets would have a significantly negative impact on one’s grade.

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.                                                                                     up

Extra Credit

During the semester, students may a small project for “extra credit”.  The extra credit grade can be substituted for one of the homework grades or one of the quiz grades.  The project should be arranged with the TAs.  Some suggested extra credit projects include the following:

1.      Make a short video or tutorial  (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.

Extra Credit Mini Projects must be handed in by May 5th, but we encourage you to hand them in early April.

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 handed in to Professor Orlin’s secretary, Andrew Carvalho, in E40-149. Late assignments will not be accepted. (See the exception on medical issues and family emergency below.) 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.                                                  up

Attendance for class and arriving late or leaving early

Attendance in 15.053 is not required, but it is strongly encouraged. In past semesters, students attending class regularly found the subject material much easier to learn, and performed better on the midterms and exams. Regardless of whether a student is able to attend a class, he or she is fully responsible for the material covered in the class, some of which may be covered in a different manner than in the book.

The Sloan School has asked faculty to emphasize professional behavior this year.  Students attending class are expected to arrive on time. A student arriving late may disrupt the flow of the class, and is (perhaps inadvertently) signaling a lack of professional respect. Similarly, students are expected to remain in class till the end, except when unavoidable. A student who has a conflict at the beginning of a class should E-mail Professor Orlin in advance of the class. Similarly, a student who has a conflict at the end of the class should alert Professor Orlin of his or her need to leave early.                                            up

Office Hours and Recitations

Office hours for the TA and for the Professor will be arranged early in the semester and put on the web site.

Recitations will be held on a weekly basis. Recitations are required, and occasionally will present material not covered in class.  Each student will be assigned a recitation time and TA at the beginning of the semester, and is expected to attend the assigned recitation throughout the semester.

On the Wednesday prior to each recitation, we will post on the web site a list of problems to be covered during the recitation, and any other topic to be covered in recitation. In general, the recitation problems will be similar to the ones covered on the assignment for that week, although there may be some additional topics covered as well, for example, the use of Excel Solver plus Ad Ins.        

Enrichment Recitations

This year, we are introducing one (or possibly two) recitation sections whose primary design is enrichment of the material.  Enrichment includes additional topics on spreadsheet modeling, applications, and may also have additional guest speakers.  Accordingly less time is spent on review and on homework problems.  The enrichment sections are designed for those who want to learn more about optimization in Management Science (such as the OR Concentrators) as well as those who do not need the review given in recitations. 

Students choosing the enrichment section will be asked to go to that recitation on a weekly basis, although they are permitted to attend another recitation as well in those weeks that they want the traditional review.                                                              up

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.  

For additional information, see the MIT website on academic integrity at
http://web.mit.edu/academicintegrity/

         up       

Medical Excuses and Family Emergencies

There are times in which a student must miss homework sets and/or exams because of a medical situation or a family emergency. If either of these situations arise, the student should discuss the matter at the earliest possible time with (1) his or her academic advisor, (2) a counseling dean http://web.mit.edu/counsel/www/, and (3) (subsequently) with Professor Orlin.             up

 

Homework Planning

There will be homework due on the following days: 

 

1.  Thursday, February 16 

2.  Thursday, February 23  

3.  Thursday, March 2

4.  Thursday, March 9          

5.  Thursday, March 23        
6.  Thursday, April 6

7.  Thursday, April 13

8.  Thursday, May 4

9.  Thursday, May 11

up
 
  Friday Recitations.
 

Date

Quiz

Topic

February 10

yes

Linear Programming Models and Excel Solver

February 17

yes

Linear and Non-linear Programming Models

February 24

yes

The Simplex Method

March 3

yes

Sensitivity Analysis and Duality

March 10

yes

Duality

March 14
7:30 to 9:30 PM

no

Midterm Review (Tuesday night)

March 17

no

No recitation

March 24

no

No recitation

April 7

yes

Network Optimization

April 14

yes

Network Optimization

April 19
7:30 to 9:30 PM

no

Review for Midterm (Wednesday night)

April 21

no

No recitation

April 28

yes

Integer Programming Models

May 5

yes

Decision Trees

May 12

yes

Decision Trees

May 19

no

Review for final exam

up