Math 187: Operations Research, Fall 2013

Instructor: Prof. Mohamed Omar
Email: [lastname] at hmc dot edu

Office: TLB 2418
Office hours: 6:00-7:00 M, TLB 2418, or by appointment.

Class meetings: Tues/Thurs 9:35 am - 10:50 am
Class webpage: http://www.math.hmc.edu/~omar/math187/

Course Outline

This course is an introduction to the fascinating subject of operations research, and in particular an introduction to mathematical optimization as a whole. The course will focus on theoretical aspects linear programming (optimizing linear functions subject to linear equality/inequality constraints), and the application of linear programming to various network theoretic and combinatorial problems. The beauty of optimization as a discipline is its ability to transfer rich mathematical theory immediately to applications, and we shall observe this phenomenon throughout the class. Our focus in the course, however, will be primarily on building the mathematical foundations and theory.

There is no required text for the course, notes from class will suffice. The main supplementary textbook will be "Deterministic Operations Research: Models and Methods in Linear Optimization", by David J. Rader Jr., ISBN 978-0-470-48451-7. This book will be available through the bookstore if you are interested in purchasing a copy. Another good textbook for interest is "Introduction to Linear Optimization" by Dimitris Bertsimas and John N. Tsitsiklis, ISBN 1-886529-19-1.

Course Structure

This course will have approximately twelve weekly assignments (worth 40% combined), a midterm exam (worth 25%) and a final exam (worth 35%). Assignments are due Tues 9:35 am (or another date if indicated otherwise). To expedite posting assignment solutions on the class webpage, no late assignments can be submitted. Of course, situations happen from time to time, so to accommodate, the two lowest assignment grades will be dropped. The midterm exam will be in class on Oct. 15, 2013. You will have the entire time, 9:35am-10:50am, to take the exam.

Course Policies

You are ENCOURAGED to discuss homework problems with other students (unless marked otherwise). Solutions must be written up individually, in your own words. Some problems on each assignment may be marked "NO COLLABORATION". These problems are intended to ensure students can tackle rudimentary problems on their own, as a litmus test for understanding the basics. As such, the only resources you may use are your Fall 2013 Math 187 class notes and the textbook "Determnistic Operations Research: Models and Methods in Linear Optimization", as referred to above. Also, on no collaboration problems, you may not communicate with any student about the problem (though you may talk to the instructor). Assignments should be submitted in class, Tues at 9:35 am (or another date if indicated otherwise). For the remaining problems, you may use all resources from class. You also may use the internet as a tool to further your learning of the course material. However, you should not use internet resources with the intention of seeking solutions to homework problems.

Disabilities

Students who need disability-related accommodations are encouraged to discuss this with the instructor as soon as possible.

Supplementary Notes

Supplementary Notes will be added here.

Simplex Method (Sept 17)

Revised Simplex Method (Sept 26)

Djikstra's Algorithm Example (Nov 11)

Ford Fulkerson Algorithm (Nov 13)

Network Flow Handout (Nov 14)

Class Notes

Class notes will be added here.

Date Topic Class Lecture
Sept 3 Intro to Operations Research Week 1 Tues
Sept 5 Optimality and its Alternatives Week 1 Thurs
Sept 10 Canonical Form / Basic Feasible Solutions Week 2 Tues
Sept 12 Convexity and Extreme Points/Basic Feasible Solutions Week 2 Thurs
Sept 17 Basic Feasible Solutions/Intro to Simplex Method Week 3 Tues
Sept 19 Simplex Method Week 3 Thurs
Sept 24 Two-Phase Method/Choosing Entering Variables Week 4 Tues
Sept 26 Revised Simplex Method Week 4 Thurs
Oct 1 Duality Week 5 Tues
Oct 3 Complementary Slackness Week 5 Thurs
Oct 8 LP Formulations Week 6 Tues
Oct 24 AMPL Lab Week 8 Thurs
Oct 29 Graphs and Digraphs Week 9 Tues
Oct 31 Graphs and Digraphs II Week 9 Thurs
Nov 5/7 Shortest Dipaths & Djisktra's Algorithm Week 10 Tues/Thurs
Nov 12 Network Flows Week 11 Tues Slides
Nov 14 Network Flows Week 11 Thurs Slides
Nov 19 Matroids Week 12 Tues Slides
Nov 26 ILP Formulation ILP Formulation
Dec 3 Gomory Cuts Gomory Cuts


Assignments

Assignments will be posted here.

Click here for the preamble file needed to compile the .tex files below.

Assignment 1 (Due: Sept 10)
Assignment 1(.tex)

Assignment 2 (Due: Sept 17)
Assignment 2(.tex)

Assignment 3 (Due: Sept 24)
Assignment 3(.tex)

Assignment 4 (Due: Oct 1)
Assignment 4(.tex)

Assignment 5 (Due: Oct 8)
Assignment 5(.tex)

Assignment 6 (Due: Oct 29)
Assignment 6(.tex)

Assignment 7 (Due: Nov 5)
Assignment 7(.tex)

Assignment 8 (Due: Nov 12)
Assignment 8(.tex)

Assignment 9 (Due: Nov 19)
Assignment 9(.tex)

Assignment 10 (Due: Nov 26)
Assignment 10(.tex)

Assignment 11 (Due: Dec 3)
Assignment 11(.tex)



Assignment Solutions

Assignment solutions will be posted here.

Assignment 1 Solutions

Assignment 2 Solutions

Assignment 3 Solutions

Assignment 4 Solutions

Assignment 5 Solutions

Assignment 6 Solutions 1data 1mod 2data 2mod

Assignment 7 Solutions

Assignment 8 Solutions

Assignment 9 Solutions

Assignment 10 Solutions

Assignment 11 Solutions