This version posted on: 2011-08-25

The official course title is "Introduction to Optimization Theory". However, we will try to split our time evenly between applications/modeling, theory, and methods.

Mathematical optimization is the science of finding the best (e.g. lowest cost) solution to a problem. Often, we also try to prove that it is the best, or that it is within some small percentage of the best solution. Some common examples are:

- Selecting the right amounts of various foods to meet nutritional requirements at minimum cost,
- Deciding on prices to maximize income,
- Manipulating statistical parameters to maximize a likelihood function, and
- Scheduling staff to meet customer demand levels.

An introduction to various aspects of optimization theory, including linear and nonlinear programming, primal dual methods, calculus of variations, optimal control theory, sensitivity analysis and numerical methods.

Some experience using Excel, Mathematica, Maple, or Matlab/Octave/SciLab will also be very helpful, but it is not strictly a prerequisite.

Follow-up courses: Math 436 Numerical Analysis, Math 419/519 Stochastic Math Models, various statistics classes.

Related courses:

- IOE 510 and 511 and maybe 512 at the University of Michigan's Industrial and Operations Engineering Department. Our course will be a one-semester version of those two courses combined.
- MIT Optimization course, with lots of good material available on-line.

Brief schedule:

- Wed Aug 31: First day of class
- Mon Sep 5: Labor day, university closed
- Thu Oct 6: Proposal 1 due
- Thu Oct 20: Project 1 due
- Wed Nov 23: Thanksgiving break--no classes
- Thu Dec 1: Proposal 2 due
- Mon Dec 12: last day of classes
- Tue Dec 13: Project 2 due; Final presentations 1:30 - 3:00 p.m. A HALF-HOUR EARLY!

Class meetings will be mostly interactive lectures and computer lab work, with some time to discuss homework.

Pray-Harrold 515m

andrew.ross@emich.edu

http://people.emich.edu/aross15/

(734) 487-1658, but I strongly prefer e-mail instead of phone contact.

Math department main office: Pray-Harrold 515, (734) 487-1444

Mon/Wed: 11:30-12:30 Office hours 12:30- 1:20 Math 121 in Pray-Harrold 202 1:20- 2:20 Office hours Tue/Thu: 11:30-12:30 Office hours in my office 12:30- 1:20 Math 121 in Pray-Harrold 202 1:20- 2:00 Office hours in PH 202, proceeding to PH 520 2:00- 3:15 Math 319 in Pray-Harrold 520 3:15- 4:00 Office hours in PH 520 4:00- 5:15 Math 560 in Pray-Harrold 520 Fri: No official office hours, but I'm often on campus. E-mail me to make an appointment, or drop by.

I am also happy to make appointments if you cannot come to the general office hours. Please send me e-mail to arrange an appointment.

I am definitely unavailable during the times I teach other classes:- M/T/W/R 12:30-1:20
- T/R 2:00-3:15

Many assignments in this course will be in the form of papers, which I want to be well written. Please consult with The Writing Center for help in tuning up your writing.

Our suggested (not required!) textbook is "Operations Research: Applications and Algorithms (4th revised edition)" by Wayne Winston (2004), retail price around $161 (yikes!) The price is why it's suggested but not required. My copy of the book has around 1400 pages (!). I understand that some students like to order international copies, which may have a different number of pages. I would be very suspicious of anything with less than, say, 1000 pages.

I will also be asking for your feedback at the end of many class meetings, written on a 3-by-5 inch notecard. Please pick up a pack of them (at least 25 cards); this should cost about a dollar.

We will also be using software. At least one of the following, and possibly more, is required:

- Microsoft Excel (2010 preferred), or other spreadsheet software like Gnumeric or OpenOffice (MS Works spreadsheet is not powerful enough), and
- GMPL/GUSEK, and
- Mathematica, Maple, or Matlab/Octave/SciLab

We will use the EMU-Online system. You are expected to keep an eye on your scores using the system, and get extra help if your scores indicate the need.

- Introduction to Operations Research, 8th or 9th Edition, by Frederick S Hillier and Gerald J Lieberman (2004), $166 MSRP
- Operations Research: An Introduction, 8/E by Taha (2007), $144 MSRP
- Operations Research: Applications and Algorithms (4th revised edition) by Wayne Winston (2004), $161 MSRP
- Introduction to Mathematical Programming: Applications and Algorithms, Volume 1 by Wayne L. Winston, Munirpallam Venkataramanan
- Linear Programming and Network Flows, 3rd Edition. Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali ISBN: 978-0-471-48599-5 Hardcover 744 pages December 2004 US $120.00
- Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
- Introduction to Linear Optimization by Dimitris Bertsimas, John N. Tsitsiklis
- Nonlinear Programming by Dimitri P. Bertsekas
- Linear and Nonlinear Programming, Third Edition by David G. Luenberger and Ye
- Primal-Dual Interior-Point Methods by Stephen J. Wright
- Convex Optimization by Boyd and Vandenberghe www.stanford.edu/~boyd/cvxbook/
- The Logic of Logistics : Theory, Algorithms, and Applications for Logistics Management by Julien Bramel
- Linear and Nonlinear Programming by Stephen G. Nash, Ariela Sofer
- Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods by Chinneck, John W. (EMU has an electronic subscription to it!)
- Practical Optimization: A Gentle Introduction" by Chinneck, John W. (Free online textbook!)
- An Introduction to Optimization, 3rd Edition Edwin K.P. Chong, Colorado State Univ. Stanislaw H. Zak, Purdue University Wiley
- Applied Integer Programming: Modeling and Solution Der-san Chen Robert G. Batson Yu Dang
- Response Surface Methodology: Process and Product Optimization using Designed Experiments, 3rd edition Raymond H. Myers Douglas C. Montgomery Christine M. Anderson-Cook
- AMPL: A Modeling Language for Mathematical Programming (2nd edition), by Fourer, Gay, and Kernighan
- GMPL: a free-software version of AMPL

- When Least is Best, by Paul J. Nahin

- Nonlinear Optimization with Engineering Applications, by Bartholomew-Biggs
- Optimization in Industry, edited by Ciriani and Leachman
- Building and Solving Mathematical Programming Models in Engineering and Science, by Castillo, Conejo, Pedregal, Carcia, and Alguacil
- Building Intuition, edited by Chhajed and Lowe, chapter on Knapsack Problem

Our primary goal is to teach you to be a good (or great!) optimizer. To be a good optimizer, you need:

- Good habits and procedures, just like a scientist, and
- Knowledge of common optimization models.

- Give future teachers some great ideas to show your kids how high-power math is used in the real world. You may enjoy reading Meaningful Math.
- Give computer-science students lots of interesting things to program. You may like reading this blog entry about math for programmers.
- Get everyone using Mathematica, Maple, or Matlab/Octave/SciLab.
- Teach you how to communicate your math models by writing math papers and giving math presentations.

Preliminaries 3 basic models: the diet problem (LP), pricing and production (NLP), shift scheduling (IP) Intro to Excel/Gnumeric and Matlab/Octave/Scilab convexity and concavity of sets and functions in multiple dimensions networks/graph theory concepts LP Common models: diet production planning blending network flows (min cost, max flow, shortest path) Software solutions (Excel/Gnumeric, Matlab/Octave/Scilab) Sensitivity analysis (experimental, not formula-based) Geometry of LPs NLP Linear algebra review: quadratic forms, eigenvalues/vectors Common models: L2 (least-squares) regression maximum likelihood estimators (MLEs) solving differential equations many others Software solutions (Excel/Gnumeric, Matlab/Octave/Scilab) Geometry of NLPs Solution methods for unconstrained problems Solution methods for constrained problems IP Common models: shift scheduling knapsack problems assignment problems travelling salesperson (TSP) vehicle routing problem (VRP) set covering/partitioning/packing Binary Variable techniques: fixed-cost problems Solution via branch-and-bound Cutting Planes More LP: L1 or L-infinity regression; Compressive Sensing? Solution via Simplex Method Duality/Sensitivity Analysis (formula-based) Solution via Interior Point Methods Heuristic Methods (if any time remains) Simulated Annealing Genetic Algorithms Tabu search Biomimic Algorithms (Ant-colony, etc) Dynamic Programming (if any time remains)

Regular attendance is strongly recommended. There will be material presented in class that is not in the textbook, yet will be very useful. Similarly, there are things in the textbook that are might not be covered in class, but are still very useful. If you must miss a class, arrange to get a copy of the notes from someone, and arrange for someone to ask your questions for you.

My lectures and discussions mostly use the chalkboard, along with demonstrations in Excel and other mathematical software. I do not usually have PowerPoint-like presentations, and thus cannot hand out copies of slides.

Homework will be assigned about once a week. It will sometimes be a small problem set designed to help you understand the behavior of math models. Other times, it will involve writing up a little paper on an assigned topic. All homework should be typed.

Homework papers should be submitted on-line, where they might be checked by TurnItIn.com or a similar service. This is partly to help keep you honest, and partly to help you learn acceptable ways to cite the work of others. A side benefit is that sometimes TurnItIn finds papers relevant to your work that you would not have found otherwise!

There will be no exams, unless the class demonstrates an unwillingness to be motivated any other way.

Instead of exams, we will have two projects. Your results for each will reported in a paper and a presentation to the class. You may work by yourself or in a team of 2 people, but no groups larger than 2 will be allowed. You may switch project partners at your will. Your project grades will each be split into roughly: 10 percent for the project proposal (due 2 weeks before the project), 80 percent for the written paper and actual work, and 10 percent for the presentation (subject to change). The presentations for the second project will be made during the time slot reserved for the final exam.

No scores will be dropped, unless a valid medical excuse with evidence is given. In the unfortunate event of a medical need, the appropriate grade or grades may be dropped entirely (at the professor's discretion), rather than giving a make-up. You are highly encouraged to still complete the relevant assignments and consult with me during office hours to ensure you know the material.

Your final score will be computed as follows:- 50 percent for all the homework together,
- 20 percent for the mid-term project, and
- 30 percent for the final project.

- Previous knowledge about linear algebra would be helpful in this course.
- A matlab book may be helpful.
- Don't wait until the last minute to do the homework.
- Start the homework questions immediately.
- Ask a lot of questions
- Email him when you get stuck -- his responses are always very prompt and helpful.
- You probably don't need the book, but if you're a math geek you're going to want it--it's good.
- Look into online tutorials for Excel and Matlab/Octave/Scilab.

I support students' right to observe religious holidays without penalty. To the best of my ability, I will schedule exams to not conflict with major religions' holidays. Students are to provide advance notice to the instructor in order to make up work, including examinations that they miss as a result of their absence from class due to observance of religious holidays. If satisfactory arrangements cannot be made, the student may appeal to the head of the department.

Academic dishonesty, including all forms of cheating and/or plagiarism, will not be tolerated in this class. Penalties for an act of academic dishonesty may range from receiving a failing grade for a particular assignment to receiving a failing grade for the entire course. In addition, you may be referred to the Office of Student Judicial Services for discipline that can result in either a suspension or permanent dismissal. The Student Conduct Code contains detailed definitions of what constitutes academic dishonesty, but if you are not sure about whether something you’re doing would be considered academic dishonesty, consult with the instructor.

Students are expected to abide by the Student Conduct Code and assist in creating an environment that is conducive to learning and protects the rights of all members of the University community. Incivility and disruptive behavior will not be tolerated and may result in a request to leave class and referral to the Office of Student Judicial Services (SJS) for discipline. Examples of inappropriate classroom conduct include repeatedly arriving late to class, using a cellular telephone, or talking while others are speaking. You may access the Code online at www.emich.edu/sjs.

If you wish to be accommodated for your disability, EMU Board of Regents policy #8.3 requires that you first register with the Access Services Office (ASO) in room 203 King Hall. You may contact ASO by telephone at (734) 487-2470. Students with disabilities are encouraged to register with ASO promptly as you will only be accommodated from the date you register with them forward. No retroactive accommodations are possible.

- Changes in your name, local address, major field of study, or source of funding.
- Changes in your degree-completion date
- Changes in your degree-level (ex. Bachelors to Masters)
- Intent to transfer to another school

- Dropping ALL courses as well as carrying or dropping BELOW minimum credit hours
- Employment on or off-campus
- Registering for more than one ONLINE course per term (F-visa only)
- Endorsing I-20 or DS-2019 for re-entry into the USA