| General information | Course schedule | Handouts | Project | Homeworks | Presentations |
| Dec 15, 2007 | Solutions to the practice final | |
| Dec 11, 2007 | Review Session: Sunday 16th, 11am-1pm, 141 MCCONE Hall | |
| Dec 10, 2007 | Here is the practice final. | |
| Dec 10, 2007 | Final Exam: BOTH SECTIONS: Bechtel Auditorium TUESDAY, DECEMBER 18, 2007 (5-8P) | |
| Dec 05, 2007 | Suggested problems for critical path method: 8.4.5a, 8.4.6a, 8.4.12, 8.4.13 (Do not give the "Free Float" which was not covered in class, --we only covered the "Total Float"="Slack"="Free Slack") |
|
| Nov 25, 2007 | As announced, on Wed Nov 21st Prof. Hochbaum covered Minimum Spanning Trees. The handouts for such class are posted. Additionally you should read section 8.6 of the book. | |
| Nov 19, 2007 | If you turn in your homework/project in my mailbox it must be before Wednesday at 3pm (as always no late submissions will be accepted) | |
| Nov 19, 2007 | On Wednesday class Prof. Hochbaum will talk about Minimum Spanning Trees (MST). For those leaving early, I will create and post a handout about MSTs, and you can also read it on the book. | |
| Nov 19, 2007 | On Wednesday you should be turning in homework # 11. Those leaving early can turn it in my mailbox. My mailbox is located at the north side of Etcheverry hall, fourth floor. Just take the north elevator of etcheverry and the mailboxes will be to your left. | |
| Nov 19, 2007 | On Wednesday you should be turning in your project. Those leaving early can turn it in my mailbox can leave it on my mailbox (under your own risk!) | |
| Nov 19, 2007 | On Wednesday there will be no discussion section, so that not only those taking the discussion on Friday are the lucky ones :) | |
| Nov 19, 2007 | There will be no homework assigned over the holiday :) | |
| Nov 17, 2007 | For the sudoku part of the project: Don't forget to include an ELECTRONIC version (i.e. in a CD) of your model file and a (sample) data file along with your project. I will run this files! I WILL NOT ACCEPT LATER THIS FILES! | |
| Nov 08, 2007 | Final Exam: BOTH SECTIONS: Bechtel Auditorium TUESDAY, DECEMBER 18, 2007 (5-8P) | |
| Nov 08, 2007 | Discussion notes for this week. | |
| Nov 04, 2007 | No class on Monday Nov 5th (due to the INFORMS conference at Seatle). | |
| Nov 04, 2007 | No office hours on Monday and Tuesday (you are welcome to email your questions to Erick) | |
| Oct 26, 2007 | How to use AMPL on the DECF machines tutorial. | |
| Oct 26, 2007 | Solutions to the midterm. | |
| Oct 19, 2007 | Solutions to the practice midterm. | |
| Oct 18, 2007 | Here is how to help a mouse! (i.e. the solution to the optional project). | |
| Oct 16, 2007 | I will have extra office hours: Friday October 16th 3-6pm (1116 Etcheverry) | |
| Oct 16, 2007 | I will give a review section on Thursday October 18th from 5-6:30pm in 145 Dwinelle | |
| Oct 16, 2007 | Practice Midterm | |
| Sep 24, 2007 | Here is the ``Help a mouse!'' optional project. | |
| Sep 19, 2007 | Here is my atempt to explain the truth table for the implication operator | |
| Sep 18, 2007 | Here is how to solve an IP with LINDO | |
| Sep 17, 2007 | Erick's office hours changed (see below for the current times). | |
| Sep 05, 2007 | Prof. Hochbaum's office hour is changing to Tue 12-1pm. | |
| Sep 05, 2007 | Midterm will take place late afternoon or evening of Oct 22 (instead of class session). Time and place will be announced. | |
| Sep 05, 2007 | Homework "0" can be picked up from a box in front of Prof. Hochbaum's office. | |
| Sep 05, 2007 | Weekly assignments are now due on class section. That is, Wed by 2:10pm at the latest (the beginning of section 1 class) or earlier at Wed 1-2pm in section 2 class. Assignments cannot be turned in the mailbox anymore. | |
| Sep 05, 2007 | Assignments cannot be turned in the mailbox anymore. | |
| Sep 05, 2007 | Section 2's classes will start at 1:05 and end at 1:55 instead of 1:10-2:00. | |
| Sep 05, 2007 | Due to the new section the office hours have changed. See new office hours posted in the General information section. | |
| Sep 04, 2007 | New section opened: MW 1-2P, 123 WHEELER (those in waiting list please change via Telebears) | |
| Aug 31, 2007 | You can also download LINDO from here. | |
| Aug 31, 2007 | SINCE: No classes on Monday THEN: Office hour will be on Tuesday Sep 4th, 2007 from 10am to 11am (1116 Etcheverry) | |
| Aug 31, 2007 | Solution to the Oranges Problem (Book problem 3.8.2) | |
| Aug 27, 2007 | Welcome to IEOR 160 - Operations Research I (Fall 2007) ! |
This course introduces the students to quantitative modeling and formulation of optimization problems, as well as to algorithms and methodologies for solving various types of optimization problems. This course aims to help the students develop modeling and optimization skills for solving problems faced in industrial engineering as well as in other engineering fields. As part of the course the students will learn to use AMPL to model and solve optimization problems. The course material does not include methodology for solving linear programming, which is covered in a companion course, except to the extent needed to use for solving integer programming problems.
Throughout the course we will develop and analyze mathematical optimization models for various production/inventory planning and scheduling, equipment replacement, transportation problems. These models will then be solved using the methods introduced during the course. The emphasis will be on modeling optimization problems as linear programming (LP), integer programming (IP) and network flow models.
The methodologies and algorithms include: branch and bound, and other IP techniques, network flow algorithms, dynamic programming, and nonlinear optimization algorithms. We will discuss the type of situations for which each methodology is appropriate.
| Homework | 15% | ||
| Project | 15% | ||
| Midterm | 25% | ||
| Final | 45% |
| Lectures | Topic | Reading | Dates |
| 1 | Course introduction | Aug 27 | |
| 2-3 | Linear programming (LP) modelling | Ch. 3.4-3.12 | Aug 29, Sep 5 |
| 4 | Graphical method solving LP in 2 variables | Ch. 3.2 | Sep 10 |
| 5 | Introduction to integer programming | Ch. 9.1 | Sep 12 |
| 6-8 | Integer programming modeling | Ch. 9.1-9.2 | Sep 17, 19, 24 |
| 9-11 | Integer programming: branch and bound | Ch. 9.3-9.6 | Sep 26, Oct 1, 3 |
| 12 | Integer programming: Implicit enumeration | Ch. 9.7 | Oct 8 |
| 13 | Integer programming: Cutting planes algorithm | Ch. 9.8 | Oct 10 |
| 14-15 | Network flows | Ch. 7.1,8 | Oct 15, 17, 22, 24, 29, 31 |
| Midterm exam | Oct 22 | ||
| 16-18 | Network flows | Ch. 7.1,8 | Oct 24, 29, 31 |
| 19-22 | Nonlinear optimization | Ch. 12 | Nov 5, 7, 14, 19 |
| 23-25 | Dynamic programming | Ch. 13 | Nov 21, 26, 28 |
| 27 | Game theory / Heuristic methods | Ch. 11 / 14 | Dec 3, 5 |
| Final exam | Dec 18 (5-8P) |
| Handout 0 | Course Syllabus |
| Handout 1 | LP Modeling |
| Handout 2 | Transportation Problem |
| Handout 3 | Make-or-buy problem |
| Handout 4 | LINDO solution for problems in Handout 01 (LP Modeling) |
| Handout 5 | Graphical method for LP |
| Handout 6a | Introduction to Integer Programming |
| Handout 6b | Captial Budgeting |
| Handout 6c | Facility Location |
| Handout 7 | IP models for piecewise linear objective functions |
| Handout 8 | Branch and Bound Algorithm |
| Handout 9 | Balas' Additive Method for Implicit Enumeartion (Exmaple) |
| Handout 10 | Balas' Additive Method for Implicit Enumeartion (Description) |
| Handout 11 | Minimum Cost Network Flows: Introduction.pdf |
| Handout 12 | Minimum Cost Network Flows Example: Chair Production |
| Handout 13 | Minimum Cost Network Flows Example: Individuals to tasks |
| Handout 14 | Shortest paths |
| Handout 15 | Equipment Replacement |
| Handout 16 | Maximum Flow |
| Handout 17 | Prim's algorithm for MST |
| Handout 18 | Application of MST |
| Handout 19 | Nonlinear programming: Economic Order Quantity (EOQ) |
The project will consist on two modeling and computational problems (to be solved in AMPL). This project will be worked on by teams of 3 or 4 people. The project's description will be given out on Monday October 22nd, and the project itself will be due in class on Wednesday November 21st.
Here is the corrected project description (remember Part 1 changed from the one given in class).For the sudoku part of the project: Don't forget to include an ELECTRONIC version (i.e. in a CD) of your model file and a (sample) data file along with your project. I will run this files! I WILL NOT ACCEPT LATER THIS FILES!
| AMPL Tutorial | Written by Prof. Kaminsky, and modified by Dr. Rajan. | ||
| AMPL Webpage | Download a free AMPL student version. | ||
| AMPL Book | Download the first chapter of the AMPL book in pdf format. |
Homeworks are due by Wednesday at noon in the GSI mailbox located at the north side of the 4th floor of Etcheverry hall. Late homework will not be accepted.
| Homework | Description | ||
| Homework 1 | Book problems: 3.1.4, 3.13.5, 3.13.6, 3.13.9 (Ch. 3 Section 13 = Review Problems of Ch. 3) | Problem 3.13.9 | Solution |
| Homework 2 | Book problems: 3.5.1, 3.13.2, 3.13.12, 3.13.48, 3.13.50 (for problems 12, 48 and 50: formulate and solve with LINDO) | Ch3.5, Ch3.13 | Solution |
| Homework 3 | Book problems: 3.13.26, 3.13.28, 3.13.47, 9.2.2 (for problem 3.13.47: formulate and solve with LINDO). Also do this problem | Ch9.2 | Solution |
| Homework 4 | Book problems: 9.2.27, 9.2.29, 9.2.32, 9.2.38 (for all book problems formulate and solve with LINDO). Also do this problem | Solution | |
| Hw 5 (part I) | Model and solve in LINDO: Problem 3 of Handout 7, Handout 6c, Book problem 9.2.31 | ||
| Hw 5 (part II) | Solve by B&B (by hand): Book problem 9.3.4, The extra problem on Hw4 (this problem) | Ch9.3 Solutions_in_AMPL |
Solution |
| Hw 6 (part I) | Model and solve in AMPL (you must print your model file and your data file): 9.3.9, 9.5.1, 9.7.22 | Ch9.7 | Solution |
| Hw 6 (part II) | Solve by B&B (branch on the 'most promissing node' and on the 'integer variable that has fractional value': 9.4.1, 9.5.3 | ||
| Hw 7 (part I) | Solve problems 1 and 2 on page 545 using Balas' additive method (the one given in the handout --NOT the one given in the book) | Page 545 | Solution |
| Hw 7 (part II) | For problems 9.5.1, 9.5.2 and 9.5.3 give the knapsack formulation using only binary variables, solve the LP relaxation (by hand), and give a cover cut (as shown in class) that 'cuts' the optimal solution of the LP relaxation. | Ch9.5 | Corrected Solution |
| Hw 7 (part III) | Solve problem 8.5.3 | Ch8.5 | |
| Hw 8 (part I) | Book problems: 8.5.7, 7.1.1, 7.1.2, 7.1.10 | Solution | |
| Hw 8 (part II) | This Problem | ||
| Hw 9 | Book Problems (formulate as SP and solve by hand with Dijkstra's algorithm): 8.2.2, 8.2.5, 8.2.7, 8.2.8, 8.2.9 | Ch8.2 | Solution |
| Hw 10 | Book Problems: 8.3.8, 8.3.12, 8.3.13, 8.3.14, 8.3.16 | Ch8.3 | Solution |
| Hw 11 | Book Problems: 8.3.3(don't set up th LP, just find the max flow and the cut), 8.3.5, 8.3.9, 8.3.10 | Ch8.3 | Solution |
| Hw 12 (Part 1) | Book Problems: 8.6.1, 8.6.2, 12.2.1a, 12.2.2, 12.3.1, 12.3.2, 12.3.3, 12.3.4, 12.3.5 | Ch8.6 | |
| Hw 12 (Part 2) | Book Problems: Solve using the BINARY SEARCH method (given in class and found in the posted presentation): 12.5.1, 12.5.2 | Solution | |
| NOT A HW | Suggested problems for critical path method: 8.4.5a, 8.4.6a, 8.4.12, 8.4.13 (Do not give the "Free Float" which was not covered in class, --we only covered the "Total Float"="Slack"="Free Slack") |
Solution |
We thank Prof. Jim Orlin for making his presentations available.
| 2007-09-17 Presentation | |||
| 2007-09-19 Presentation | |||
| 2007-09-24 Presentation | |||
| Ship Loading Problem | Thanks to John Baumler for creating this presentaton. | ||
| 2007-10-01 Presentation | |||
| 2007-10-10 Presentation | |||
| Shortest paths presentation | |||
| 2007-11-29 Nonlinear |
