# Fall Semester 2011

## Basic Information

Note: this syllabus is temporary, and may change up to the first day of class.
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.
Since you have had the prerequisite courses, you are familiar with finding the minimum or maximum of a function (like in first-semester calculus), and finding the minimum or maximum of a function of two or three variables (like in third-semester calculus). In this course, we will be working with thousands of variables--real applications can use millions of variables. Of course, we don't solve problems like that by hand. In our course, we will learn the methods people have developed for computers to solve such large problems.

### Official Course Catalog Entry

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.

### Prerequisites

Completion of courses in linear algebra and multivariable calculus is assumed.
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:

• Convex Optimization lecture videos from Stanford

### Class Meetings

CRN 17193: Tue, Thu 4:00pm-5:15pm in Pray-Harrold 520
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!
3 credit hours.

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

### Instructor information

Professor Andrew Ross
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

### Office Hours and other help

Here is my complete schedule.
```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.

### Required materials

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

#### Course Web Page

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.

#### Supplementary Materials

Here are some handy web sites: Here are some other optimization books:
• 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
Other books related to optimization, but not really our main focus:
• When Least is Best, by Paul J. Nahin
Books on Optimization Models:
• 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

## Course Content

### Course Goals

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.
We have a few secondary goals, which may be more or less applicable to your personal situation:
• 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.

### Outline/schedule

Many classes in optimization theory start with linear problems and solution methods, then proceed to nonlinear problems, because linear problems and solution methods are simpler. Other classes start with nonlinear, because then linear is just a special case. We will start with mostly nonlinear problems and solution methods because then you will have a wide base of ideas to do the first (mid-semester) project.
```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)
```

#### Attendance

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

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!

#### Exams

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

#### Project(s)

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.
Once final scores are computed, a curve will be applied.

### General Caveat

The instructor reserves the right to make changes to this syllabus throughout the semester. Notification will be given in class or by e-mail or both. If you miss class, it is your responsibility to find out about syllabus and schedule changes, especially the due dates and times of projects, assignments, or presentations.

Last time I taught the course, I asked my students to give advice to you, future students, based on their experiences in my course. Here are some of the highlights:
• 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.

## Standard University Policies

### Religious Holy Days

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.

### Classroom Behavior

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.

### Special Needs Accomodations

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.

### Student and Exchange VISitors (SEVIS)

The Student Exchange Visitor Information System (SEVIS) requires F and J students to report the following to the Office of International Students, 229 King Hall within ten (10) days of the event:
• 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
Prior permission from OIS is needed for the following:
• 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
Failure to report may result in the termination of your SEVIS record and even arrest and deportation. If you have questions or concerns, contact the OIS at 487-3116, not your instructor. Also, see the EMU SEVIS page.