Pietro Belotti

Meeting: Mohler Lab 453, Tue/Thu, 1:45pm-3:00pm.

Click here to get a copy of the syllabus.

• Quiz #1: 09/30/08, 1:45pm-3:00pm (Solution).
• Quiz #2: 11/04/08, 1:45pm-3:00pm (Solution).
• Final exam: 12/09/08, 12:00pm-3:00pm, Packard 416.
• Case study page.
• Fun with Integer Programming: http://www.chlond.demon.co.uk/academic/puzzles.html
• Some extra material on the Minimum Spanning Tree problem, the Network Design Problem, and on how to use graphs in AMPL.
• See also the page on Opportunities for students.

Lecture calendar

1. 08/26/08: Introduction. Variables, Constraints, Objective function (notes).
2. 08/28/08: Convexity, relaxations (notes).
3. 09/02/08: Relaxations, lower and upper bounds. Linear Programming (notes).
4. 09/04/08: Examples of Linear Programming problems. Brief introduction to AMPL (notes).
5. 09/09/08: Graphically solving LPs. The simplex method. Sensitivity analysis (notes).
6. 09/11/08: More LP examples with AMPL. Sensitivity analysis (notes).
   Homework 1. Solution of homework 1. Brief IIS howto.
7. 09/16/08: Min-max, max-min problems (notes).
8. 09/18/08: Goal programming (notes, corrected). Examples:
   • goal programming ex. 1 (non-preemptive, preemptive-stage1, preemptive-stage2).
   • Smallville (non-preemptive, preemptive-stage1, preemptive-stage2, preemptive-stage3, preemptive-stage4, min-max).
9. 09/23/08: Network flows (notes).
10. 09/25/08: Quiz practice (notes).
11. 09/30/08: Quiz. Solution.
12. 10/02/08: Integer Programming (notes).
13. 10/07/08: Graph optimization, fixed charge models, NEOS (notes). Examples:
    • Edge covering (mod, dat, run).
    • Node packing (mod, dat, run).
    • Production planning with fixed charge (mod, dat, run).
14. 10/09/08: Implications, relaxations. (notes).
15. 10/16/08: Formulations. Branch&Bound. (notes).
    Homework 2. Due October 23. Solution of homework 2.
16. 10/21/08: The Traveling Salesperson Problem. The Quadratic Assignment Problem. Piecewise linear functions (notes).
17. 10/23/08: Modeling exercises: The minimum spanning tree problem, Network design, Mining. (notes).
18. 10/28/08: Nonlinear Programming: convex functions, convex NLPs, convex MINLPs (notes).
19. 10/30/08: Quiz practice (notes).
20. 11/04/08: Quiz. Solution.
    Homework 3. Due Wednesday, November 12. Solution.
21. 11/06/08: Least squares approximation. Quadratic programming (notes).
22. 11/11/08: Lagrangian Relaxation. Optimality conditions for NLP (notes).
23. 11/13/08: Lagrangian Relaxation on Knapsack. KKT, examples. Multi-criteria optimization (notes).
24. 11/20/08: Introduction to Stochastic Programming (notes).
25. 11/21/08: Stochastic Programming (notes). Examples (just run your local version of ampl, no need for a data file):
    • Farmer (Deterministic model with perfect information, Stochastic Programming model, Stochastic Programming – Max/Min model).
    • Three-stage SP model (Deterministic model with average value, Model with perfect information, Stochastic Programming model).
26. 11/21/08: Stochastic Programming – Examples (notes).
    Homework 4. Due Thursday, December 4. Solution.
27. 12/02/08: Stochastic Programming – the newsvendor problem (notes). Example: newsvendor.mod.
28. 12/04/08: Exam practice (notes).

Modeling language

My favorite modeling language is AMPL, but you are encouraged to use whatever language you prefer. For those who don’t know what to pick, some alternatives are GAMS, Lindo, and Mosel. The latter has a good manual that also serves as an introduction to modeling.

Both AMPL and Mosel have student versions that can be downloaded for free. They are are limited to a maximum of 300 constraints and variables, but this is more than enough for most of this course.

Here are the instructions for downloading and using AMPL. There are also some examples we did in class: tin can, knapsack, post office, diet, financial planning, and  project selection.

Note: clicking these .mod files may suggest Windows that these are music files, as .mod is a common extension for some type of music files. You may want to right-click them and select “Save link as…” instead.

Problems formulated in AMPL or GAMS can be solved by submitting the model at http://www-neos.mcs.anl.gov/neos. Many solvers can be used for free, and with no limits on the number of constraints and variables.

Course material

Chapters of the book by R. Fourer: chapter 1, chapter 2, chapter 3.

Accommodations for Students with Disabilities

If you have a disability for which you are or may be requesting accommodations, please contact both your instructor and the Office of Academic Support Services, University Center C212 (610-758-4152) as early as possible in the semester. You must have documentation from the Academic Support Services office before accommodations can be granted. For more information, please visit the student support services website: http://www.lehigh.edu/~inacsup/disabilities.