Office hours on two Tuesdays: March 14 and 21, 1-2:30pm, in 775 Evans

Office hours on two Wednesdays: March 15 and 22, 2:30-4:00pm, in 925 Evans

Last Day of Class: Thursday, April 27

Midterm Exam: Thursday, March 2

Term Papers Due: Thursday, May 11

Basics of mathematical software (e.g. SAGE, Maple, or Mathematica)

To brush up on MATLAB, consider enrolling in Math 98 this semester.

by Dimitris Bertsimas and John N. Tsitsiklis, Athena Scientific 1997.

2. Geometry of Linear Programming

3. The Simplex Method

4. Duality Theory

5. Sensitivity Analysis

7. Complexity and the Ellipsoid Method

8. Interior Point Methods

10-11. Integer Programming

The sections to be covered in each lecture are listed below. Please read these before coming to class.

**Grading:**
There will be weekly homework sets and a midterm exam (in-class).
The midterm covers Chapters 1,2,3,4.

The final is a term paper (take-home).
The grading scheme is:
**Homework 35%,
Midterm 30%,
Term Paper 35%**.

**Homework:**
There will be a weekly homework assignment,
to be handed in on Tuesdays at 11:00am, at the end of class.

Late homework will not be accepted. No exceptions.
The assignments, posted below, refer to the text book.

No homework after spring break, so you can focus on your term paper.

**Midterm Exam:**
The midterm covers
the first four chapters and is
held in class on Thursday, March 2.

This is an open book exam.
The exam and solutions are posted
here.

**Final Exam:** You will write a term paper on a topic
of their choice related to the class. This can focus on
foundational

mathematics (e.g. geometry
and combinatorics of convex sets), or
involve computing and software, or develop an

application of
optimization that interests you. Your choice. You may work on this by yourself or in teams of two.

Please submit a proposal for your project
by Thursday, March 23. This should fit on
one page and contain:

names of author(s), title,
sources, and a brief description.
The final version of the paper is due on Thursday, May 11.

**Student Presentations:**
Short talks on the term papers are scheduled
for April 24,25,26,27.

Click
here
for the schedule. Registered students
are expected to attend all lectures.

** DAILY SCHEDULE: **

Jan 17: 1.1 Variants, 1.2 Examples, 1.3 Piecewise linear convex objective functions

Jan 19: 1.4 Graphical solution, 2.1 Polyhedra and convex sets

Jan 24: 2.2 Vertices, 2.3 Standard form, 2.4 Degeneracy

Jan 26: 2.5-2.6 Existence and optimality of extreme points,2.7 Bounded polyhedra

Jan 31: 2.8 Fourier-Motzkin elimination, 3.1 Optimality conditions

Feb 2: 3.2-3.3 Simplex method

Feb 7: 3.4 Anticycling, 3.5 Phase One, 3.6 Column Geometry

Feb 9: Mathematical Software for Optimization

Feb 14: 3.7 Computational Efficiency, 4.1 Motivation for Duality

Feb 16: 4.2 Dual problem, 4.3 Duality theorem

Feb 21: 4.4 Marginal cost, 4.5 Dual simplex method

Feb 23: 4.6 Farkas Lemma, 4.7 Separating hyperplanes, 4.8 Cones

Feb 28: 4.9 Representation of polyhedra, Review

Mar 2: MIDTERM EXAM

Mar 7: 5.2 Global dependence on right-hand side, 5.3 Set of dual optimal solutions

Mar 9: 5.4 Global dependence on cost, 5.5 Parametric programming

Mar 14: 10.1 Modeling techniques, 10.2 Guidelines for strong formulations

Mar 16: 10.3 Modeling with exponentially many constraints, 11.1 Cutting plane methods

Mar 21: 11.2 Branch and bound, 11.3 Dynamic programming

Mar 23: 11.4 Integer programming duality

Apr 4: Interior point methods

Apr 6: Semidefinite programming

Apr 11: Polynomial optimization via sums of squares

Apr 13: No class: work on term paper

Apr 18: No class: work on term paper

Apr 20: No class: work on term paper

Apr 24, Mon 5-7pm (939 Evans Hall): Student presentations

Apr 25, Tue 9:30-11am (3107 Etcheverry): Student presentations

Apr 26, Wed 5-7pm (939 Evans Hall): Student presentations

Apr 27, Thu 9:30-11am (3107 Etcheverry): Student presentations

** Homework assignments: **

due Jan 24: (Section 1.7) Exercises 1.1, 1.4, 1.7, 1.8, 1.12, 1.14, 1.19

due
Jan 31: (Section 2.10) Exercises 2.1, 2.3, 2.4, 2.6, 2.7, 2.9, 2.10

due Feb 7: (Sections 2.10 and 3.9) Exercises 2.18, 2.21, 2.22,
3.2, 3.3, 3.5, 3.6, 3.10

due Feb 14: (Section 3.9) Exercises 3.16, 3.17, 3.19, 3.20, 3.22, 3.26, 3.28, 3.29, 3.30

due Feb 21: (Section 4.12) Exercises 4.1, 4.2, 4.4, 4.5, 4.6, 4.12, 4.13, 4.16

due Feb 28: (Section 4.12) Exercises 4.21, 4.24, 4.25, 4.29, 4.30, 4.31, 4.35, 4.36, 4.39

due Mar 14: (Section 5.7) Exercises 5.3, 5.8, 5.10, 5.11, 5.13, 5.15

due Mar 21: (Sections 10.5 and 11.10) Exercises 10.1, 10.5, 10.10, 10.12, 10.14, 11.1, 11.2, 11.3