Applied Mathematics 121 is a journey into the mathematical ideas and computational methods for solving deterministic and stochastic optimization problems. This course is offered in Spring 2013. Lectures will meet on Mondays and Wednesdays, 1-2:30pm at Maxwell Dworkin 119 (note the location change).
Optimization is the problem of making decisions to maximize or minimize an objective in the presence of complicating constraints. The class will take you on a journey through the theory, methods, and application of linear programming, integer programming, Markov chains, and Markov decision processes. You will learn the methods, understand them, practice them, and apply them to problems in business, society, engineering, sports, e-commerce, and medicine. Optimization can bring efficiency throughout society and wherever resources are constrained. Optimization is also used in the design and analysis of engineered systems of all kinds. Linear programming and the beautiful simplex method is at the heart of the class and is the engine for solving optimization problems on a massive scale.
We emphasize modeling, the process of taking a real world problem and transforming it into a formulation that can then be solved by the methods we have developed. Our approach is hands-on and our attitude is can-do: we will examine problems that arise in the world, formulate them into models, and solve them. Interactive team exercises will form part of the class. We will have help from computers, and learn how to use their powers to solve these difficult problems.
See the course schedule for a week to week breakdown of the course.
Officially, Applied Mathematics 21b or Mathematics 21b (or Math 23, 25, 55) and some knowledge of probability and statistics at the level of Statistics 110 or Engineering Sciences 101. Unofficially, a strong desire to learn, some mathematical maturity, and comfort with computational tools will help. If you are unsure of whether you are well prepared for the course, we highly recommend you contact a member of the course staff, and just to come shop the class and see if it is for you.
We will provide links on the schedule page to several papers that will serve as supplemental readings. There is no required textbook for this class. Students may find the textbook Operations Research Models and Methods by Jensen and Bard useful. In Spring 2008, we used Applied Mathematical Programming by Bradley, Hax, and Magnanti for the first half of the course. The book is out of print, but is available online for free. You may find it useful as a second reference. We do use a bit of AMPL throughout the course. We have provided a wiki that provides all the information you need. There is an AMPL book available with advanced programming techniques, but you won’t need it.
The course staff is always happy to recommend additional readings or other sources of information if you would like to explore a topic from the course in more depth.
Most questions about the course, lecture or section material, or the assignments should be addressed via the AM121 page on the electronic discussion board, Piazza. The course instructors will regularly check the discussion board and post responses, and you will receive emails with important logistical information through Piazza. Please do not post any formulations or code from your homeworks or from the assignment solutions to Piazza. Long, detailed questions are probably best answered during office hours. Questions that are not appropriate for the discussion board may be sent to your teaching fellow. Use your judgement.
There will be (roughly) weekly problem sets. As long as an effort is put into completing each and every one of the 8 problem sets, the lowest score will be dropped when calculating the course grade. The problem sets consist of a combination of theoretical and applications based exercises, with an emphasis on (first) understanding the methods we study and (then) applying them. Some of the problem sets will require formulating and solving models in AMPL. Students will also benefit from using mathematical software such as Maple or Matlab to avoid the tedious and error-prone nature of hand-calculations. Tutorials of said software will be provided in section; reference material will be posted on the resources section of the website.
AMPL is provided at the beginning of the course. Please follow the detailed set up instructions from the guides in the resources section of the course website. Both Maple and Matlab are available from FAS Computer Services Software Download (you will also need to get KeyServer to make use of the software).
In addition to problem sets, there will be two “Extreme Optimization” assignments, one near the end of the linear programming unit, and another near the end of the integer programming unit. These assignments present students with real world scenarios: large-scale problems that are non-trivial, yet (to-an-extent) solvable through the optimization techniques covered in this course. Students will work in teams, and work together to formulate basic models and refinements, implement and solve formulations using AMPL, and present their techniques and findings in class.
Each student will receive 5 late days over the course of the term, each allowing the student to turn in a homework 24 hours late without penalty. You may only use 1 late day per assignment (usually moving the deadline from 5pm Friday to 5pm Saturday). Do note that late days may not be allowed on certain homeworks preceding quizzes and/or projects. If the workload becomes particularly overwhelming during a week of the semester, students are reminded that as long as they show effort on each of the 8 problem sets, the lowest of the 8 scores will be ignored when calculating the course grade. In cases of medical or other emergencies which interfere with your work, have your tutor or Resident Dean contact the instructor.
Your grade will be calculated as a weighted average of your scores on problem sets, extreme optimization assignments, and two out-of-class evening quizzes. If taking the course pass/fail, you must achieve a passing grade in each of the three major components in order to pass the course. The percentage breakdown (subject to change) is 30% problem sets, 20% extreme optimization, and 50% for the quizzes. There will not be a final exam.
We will also drop the lowest weight problem set score, conditional on your having put in a good faith effort into every single assignment.
All problem sets should be written up individually. All extreme programming assignments are to be completed in teams (usually teams of four).
For problem sets, students are strongly encouraged to collaborate in planning and thinking through solutions, but must write up their own solutions without checking over their written solution with another student. Do not pass solutions to problem sets nor accept them from another student. If you are ever in doubt, ask the course staff to clarify what is and isn’t appropriate.