To go directly to one of the following topics, click on the corresponding link:
New this week
General Information
Textbook
Syllabus
Slides
Class summaries
Grading
Homework
Project
Exams
Handouts
OR/MS Links
HOME
================================================
New this week (Dec. 30)
Well, this is the last message for this semester. I think it has been a very good semester,
and looking at your final exams and projects, it is clear that most of you have worked very
hard and have learnt a lot!
For everyone's benefit, I am making the final project reports available online,
feel free to browse... go to the project
directory. Have a great break and best wishes for a Happy New Year!
back to the top
================================================
New this week (Dec. 3)
The sixth homework
is available, it is due Thusday 6 December.
Program for the week
Tuesday 11/20 Nonlinear Programming III: KKT conditions. Also
Karmarkar's algorithm.
ch. 12
Thursday 11/22 Review?
ch. 0...
A reminder: Rardin's file on gams is available
here. The links may not work anymore, so that you have to navigate in the text on your own, but the summary of GAMS' main features is excellent.
back to the top
================================================
New this week (Nov. 26)
For fun!
Notice that our textbook is one of the references!!!!
Program for the week
Tuesday 11/27
Nonlinear Programming II
ch. 12.
You may want to read the following
summary on NLP.
Thursday 11/29 solving NLP by
KKT conditions
ch. 12.
Here is an example of the use of
KKT for solving an NLP problem with inequality constraints.
You can also look at these
files.
Homework
6 is available and must be returned December 6.
back to the top
================================================
New this week (Nov. 19)
The fifth
homework
is available, it is due Tuesday 27 November.
Program for the week
Tuesday 11/20 Nonlinear Programming I: convexity issues
ch. 12
Thursday 11/22 Happy Thanksgiving! See you next Tuesday!
ch. 0...
back to the top
================================================
New this week (Nov. 12)
The fifth
homework is available, it is due Tuesday 27 November.
Program for the week
Tuesday 11/13 Integer programmin: branch and bound
ch. 9, p. 475-539
Thursday 11/15 Integer programmin: cuts and Dual Simplex Method
ch. 9, p. 545-552 + handout, p. 329-335
back to the top
================================================
New this week (Nov. 5)
The 4th
homework is available, it is due Tuesday 6 November.
You got by email on Monday solutions to a set of problems from the textbook, as well as answers to two past exam questions, plus a quiz.
In addition, here is the text of last year's midterm (we were using the same textbook), but without answers.
Program for the week
On Tuesday 11/6
Sarper's
slides
for Chapter 7 on the transportation problem.
Sarper's
Slides
for Chapter 7 on the assignment problem.
On Thursday 11/8
Sarper's
slides for Chapter 9
on integer programming (part 1), as well as
Orlin's
modified slides on IP.
The mid-term exam will be take-home. It will be available at the end of class on Nov. 8
and will have to be returned at the latest by the beginning of class on November 13,
unless special arrangements have been made with the instructor.
The exam should take no more than 2 days, on and off. Which 2 days is up to the individual student.
Each student must send an email to opim910 at yahoo.com as soon as s/he starts the exam.
The honor system of the University of Pennsylvania will prevail.
There will be review sessions (Q&A type, plus problems) on Monday 4-6 (Monique), Wednesday 4-6 (Aykut), Friday 11am-1pm (Aykut).
In the OPIM Conference room, 5th floor, JMHH.
back to the top
================================================
New this week (Oct. 29)
The fourth homework is due Tuesday 6 November.
The text of the homework was updated on Thursday 1 November in the evening.
The following
gams files may be useful, in particular they illustrate the use of mpswrite.
Try to run the following gams
program,
this is the
listing,
and this is the
log file.
In gams under windows you automatically obtain the log file.
In unix, it is not automatically saved, but you can get it by running your
program in batch mode,
using the command "gamsbatch mymodel" instead of "gams mymodel".
In batch mode, you can even turn your computer off, and the run continues
in the background on the unix machine. This is useful in particular for long runs.
Look at the updated exam information.
Look at the e-optimization link.
For Tuesday's class:
(1) we will review
sensitivity analysis, p.18-21
(2) we will start looking at transportation poblems.
Download the file on
transportation problems,
as well as this
gams file and its
output.
Finally, download this
file about degenerate solutions.
back to the top
================================================
New this week (Oct. 22)
The fourth homework is due Tuesday 6 November.
Program for the week
week 8
10/18 Duality ch. 6
and 10/18 Transportation problems ch. 7
Look at the following incomplete LINDO outputs and try to figure out what the missing numbers should be and why.
1
2
The original incomplete output files and the solutions are both unprotected now, so you can open them all.
1
2
Read the following
note on duality and complementary slackness
and this
note on the possibility of an infinite duality gap.
Sensitivity analysis: change in rhs values
input
output
Print the following
file on minimum cost flow problems,
and this
file on getting the dual problem,
for the class on Thusday.
back to the top
================================================
New this week (Oct. 15)
The third
homework is available, it is due Tuesday 23 October.
Program for the week
week 7 10/18 Sensitivity Analysis-Applied - special cases
and interpretation ch. 5 and ch. 6
back to the top
================================================
New this week (Oct. 8)
The third
homework is available, it is due Tuesday 23 October.
Program for the week (from the syllabus)
week 6 10/9 and 11 Sensitivity Analysis-Applied-I and II
and Sensitivity Analysis-Duality-I,
ch. 5 and ch. 6
back to the top
================================================
New this week (Oct. 1)
The second
homework is due Tuesday 9 October (notice the change!).
Program for the week (from the syllabus)
week 5 10/2 2-Phase Method and Big-M Method ch. 4
week 5 10/4 Sensitivity Analysis-Applied-I,
ch. 5, Sections 5.2 to 5.4.
The answer key for homework 1 has been emailed to you, and a note on grading are available in the homework section.
It has come to my attention that the excellent textbook Applied Mathematical Programming, by Bradley, Hax and Magnanti, although out of print, is available
online. I would encourage
you to read at least parts of it, as it provides another perspective, and it may help you better understand some difficult concepts.
The following
webpage has links to a number of potentially interesting sites.
back to the top
================================================
New this week (Sept. 24)
The second
homework is available, it is due Tuesday 9 October (notice the change!).
Program for the week (from the syllabus)
week 4 9/25-27 Simplex Method-II ch. 4
back to the top
================================================
New this week (Sept. 10)
When you install the CD from the back of the textbook on your computer, you will
notice that LINDO and LINGO will be installed automatically, among other things.
Be sure that you are connected to the internet at this point, as the system will look
for a possible update on the LINDO site (and chances are there is a newer version
than that on your CD). The good news is that you don't have to go to the LINDO site
to download the LINDO package on your own, this will be done automatically.
Be sure to read the following Operations Research
success stories.
You can read about these and other OR projects in the journal "Interfaces", which
you can access online on the Penn Library site. Click
here
and choose the first "Interfaces" on the list.
The first
homework is available, it is due Thursday 20 September.
back to the top
================================================
G. B. Dantzig, the father of Linear Programming, passed away in May 2005.
Read the article, or this
one entitled
"G. B. Dantzig 1914 - 2005", in the Bulletin of the Czech Econometric Society 22 (2005),
by J.Dupacova and D.P.Morton.
================================================
Operations Research: the science of better.
Click on "Benefit", then "Optimize Resource". Look at the examples.
================================================
You may look online at (but not print) the following
book on optimization. This book is used in OPIM 913, Advanced Linear Programming. You might want to at least glance through it occasionally.
font size=4>back to the top
================================================
General Information
Course Description
Optimization problems arise in a wide variety of systems including
manufacturing systems, transportation systems, financial systems, and
telecommunication systems. This course covers major mathematical
models of optimization problems -- linear programming, network flow,
integer programming, and nonlinear programming. We will focus on
formulation issues and solution methodologies for these classes of
optimization models. We will use several optimization software
packages, first the easy-to-use commercial packages, LINDO
and possibly EXCEL. These are good for small problems but data entry can be tedious.
Another class of solvers work on algebraic formulations, and are useful in
particular when one must solve several problems with the same structure,
such as transportation or assignment problems. One of these is LINGO,
an extension of LINDO, also available on the CD that comes with the text.
Another one is GAMS (General Algebraic Modeling System). It
is both an interface between us, the users, and commercial "solvers",
i.e., software packages that are designed to solve one or more of the
model types mentioned above, and a language, in which one can write
models and to some extent algorithms for solving them, using, or not,
the solvers provided. GAMS is available on a number of servers on campus. In
addition an academic demo version can be downloaded from the GAMS
website (look for information, documentation, and links, at
http://www.gams.com.,
http://www.gams.com/presentations/orms_sungrid.pdf,
and
http://www.gamsworld.org.)
Please also go to this
site .
back to the top
You can look at the following gams files taken from Ron Rardin's site and
the output files that I generated:
cfpl.gms
cfpl.lst
cfpl.log
tubprods.gms
tubprods.lst
tubprods.log
To learn how to "include" files in a gams file, read the file
includes.pdf and
conditional_compile.pdf.
In addition if you are an EMACS user, you might be interested in the following link:
http://park.zero.ad.jp/~zbc08106/gams/gams.html .
back to the top
Audience
This course is intended as a first course in Mathematical Programming
for graduate students in engineering, mathematics, statistics,
marketing and operations management/research. This section is
specially designed for doctoral students, who will most likely take
some more advanced courses after this one, such as Advanced Linear
Programming, Advanced Nonlinear Programming, Advanced Integer
Programming, Graph Theory, and so on. More emphasis will be placed on
algorithms, the underlying theory, and on matrix representations.
back to the top
Background
This course assumes elementary background in multivariate differential calculus and in linear algebra, plus familiarity with vector/matrix notation and arithmetic.
Instructor and TA
Prof. Monique Guignard-Spielberg
Office: 5th floor, OPIM Dept., JMHH
Phone: 215-898-8235
Email: guignard@wharton.upenn.edu
URL: http://opim.wharton.upenn.edu/~guignard
Office Hours: Wednesday, 4-6 pm, in my office (5th floor, JMHH) and by appointment.
The TA for the class is Aykut Ahlatcioglu (OPIM Ph.D. student).
Office: 5th floor, OPIM Dept., JMHH
Email: aaykut@wharton.upenn.edu
Office hours: Monday 4-6 pm, in his office (5th floor, JMHH) and by appointment.
Office hours will start the week of September 17.
The teaching team can be reached at the following email address:
opim910@yahoo.com
back to the top
Textbook
The textbook used for the course is
"Introduction to Mathematical Programming," by W. L. Winston and M. Venkataramanan, Thomson, 4th edition.
back to the top
Course Syllabus
Students must read the material before class. The material covered in class will often differ from the readings, as the emphasis will be more on concepts and on more rigourous presentations of algorithms, using matrix notation and higher dimension problems. Homeworks will cover both the chapter material and class material.
The syllabus for fall 2007 can be found
here.
back to the top
Slides
Class #3
Orlin's modified Chapter 3-A slides, the EXCEL
file
and the LINDO
input file.
Here is a simple DOS file to execute
LINDO. It is very portable, but not as flexible as the Windows version. Also it is an older version.
Notice that you probably have to download it and run it from the command line on your PC.
Week 4
Orlin's modified
slides for Chapter 4, part 2,
on the simplex method,
and the LINDO
input file.
Summary of class of 19 September 2006.
You may also want to look at the following
file for Chapter 4 by H. Sarper.
Week 6
Orlin's modified
slides for Chapter 6
on sensitivity analysis on a financial problem.
Orlin's modified
slides for Chapter 6
on reduced costs and shadow prices,
and the corresponding
excel sheet .
Week 7
No slides, see under "New this week" for reading material.
Week 8
Sarper's
slides for Chapter 7
on the transportation problem.
Week 9
Sarper's
slides
for Chapter 7 on the transportation problem.
Slides
for Chapter 7 on the assignment problem.
Sarper's
slides for Chapter 9
on integer programming (part 1), as well as Orlin's
modified slides on IP.
back to the top
Grading Policy
- Project: 25%
- Homework: 25%
- Midterm Exam: 25%
- Final Exam: 25%
back to the top
Class Summaries
back to the top
Homework
back to the top
Term Project
It would be especially interesting if projects could be based on optimization
problems arising on campus: dining, transportation, heating/cooling, recycling,
medical care, maintenance, scheduling, etc...
One-page proposals for the projects should be returned on Thursday 4 October. They should
also be sent as electronic files to opim910 at yahoo.com before that class.
You should describe the problem, the literature you are proposing to cover,
and the numerical experiments you will conduct (data collection,
comparison between solvers, model modification, ..., as applicable).
Projects should be done in groups of three or four persons.
In the final report, each member of the group will have to specify
his/her contribution to the project.
There will be a class presentation at the end of the semester (in class on Thursday 6 December),
and a written report, including the code(s) developed and the listings,
will be due at the time of the final exam.
Some earlier proposals can be found in this directory.
The GAMS file lists a certain number of projects that were done in GAMS. That may give
you ideas as to the kind of problems that could be solved by math. programming.
back to the top
Exams
The mid-term exam will be take-home. It will be available at the end of class on Nov. 8
and will have to be returned at the beginning of class on November 13. In case of conflict
with other exams, students must let the instructor know no later than October 30.
The exam should take no more
than 2 days, on and off. Which 2 days is up to the individual student. The honor system of
the University of Pennsylvania will prevail.
The final exam will be comprehensive. It will also be a take-home exam,
during the official exam period. You will be able to pick up the exam questions
any time on or after the first day of exams (Dec. 12) and return it 2 days later,
at the latest at 9 am on December 18.
back to the top
Handouts
- Handout 1:
Course syllabus & assignments, this file
- Handout 2:
Examples on formulating optimization problems,
pdf file from Dr. Zhi-Long Chen
- Handout 3:
Examples on formulating LP problems,
pdf file from Dr. Zhi-Long Chen
- Handout 4:
Look at the gams code implementing
affine scaling.
Rerun it with the other example from Rardin's book.
Think about what happens when there is more than one equality constraint.
- Handout 5:
About GAMS. In order to separate data from the program itself,
you can use the
$include file.data
feature of GAMS. At execution time, the line "$include file.data" will be replaced verbatim by the file file.data
or whatever file name you wrote after $include. Example:
look at the modified file
onbshift.gms
, it calls the following files
arr.txt,
dutyf.txt,
and
dutyp.txt
. After downloading these files, and before trying to run this on your own PC,
make sure that all the .txt files are in the directory C:\windows\gamsdir.
If you want to place them somewhere else, you have to modify the file onbshift.gms accordingly.
Notice that you have to be careful when using the
$include inside a gams file to have the right ";" where needed.
If the file to be included contains table or parameter data, it may be safer
to leave the ";" out of the included file, and let the gams file itself
decide whether a ";" is needed or not.
If you want to read more about the $include feature, look in the
GAMS notes of Rardin at the section on
included files and spreadsheet input.
back to the top
Interesting Links about Operations Research/Management Science
