================================================
back to the top
back to the top
back to the top
back to the top
back to the top
back to the top
back to the top
back to the top
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. Audience Background Instructor and TA Prof. Monique Guignard-Spielberg
A good weather channel :
http://www.wunderground.com/US/PA/Philadelphia.html ESE 504
New this week (Nov. 16)
This is week 11, classes 17 and 18..
Material for class 17 and the next ones can be found
here.
HW5 is in three parts.
The third part is available
here.
The second problem of HW5 is available
here.
Due on Tuesday after Thanksgiving.
================================================
New this week (Nov. 9)
This is week 10, classes 15 and 16.
The first problem of HW5 is available
here. Due on Tuesday after Thanksgiving.
In class, we will continue the section of Transportation/Assignment.
The book considers more general flow problems than what we will study, so
please use the slides.
Second part of HW4 available. You won't be able to compute the reduced
costs now, wait until after tomorrow's class.
Remember to append your answer to the cake baking exercise.
Due on Thursday November 12.
================================================
New this week (Nov. 2)
This is week 9.
The midterm is on November 3 during regular class time.
In class, we will start the section of Transportation/Assignment.
The book considers more general flow problems than what we will study.
Please use the slides.
First part of HW4 available. Remember to append your answer to the cake baking exercise.
Due on Thursday November 12.
================================================
New this week (Oct. 26)
This is week 8.
view the incomplete LINDO ouput files and some review material in this
folder.
First and second parts of HW3 available. Due on Thursday October 29. If you have no time
to do the cake baking exercise by Thursday, you may return it with HW4.
Homework assignments are due every two weeks, on Thursday.
Some information on the midterm:
it will be in class, closed book, but you are allowed to bring with you one page
containing as much information as you care - and manage - to put on it.
Double sided if you think it is better.
You will have to return the page with the exam, but it will be returned to you later.
No cell phones will be allowed during the exam, if you bring one, we will collect them
at the beginning and you will retrieve them at the end. Make sure yours has some distinct
feature so that you can recognize it.
The exam will be in the same style as the homework and the power point slides.
It will cover all material covered in class up to and including today.
It will consist of three problems, a modeling problem, a problem centered on solution
methods and/or sensitivity analysis, and an incomplete LINDO output.
We will practice the incomplete LINDO output in class on Thursday.
To help you prepare for the exam, there will be a session with problems on Monday
(with Ying), and I will be available on Friday 1 to 5pm in case you have questions.
In the OPIM Conference room, same as for the office hours, except that we are changing
to the one on the right, so that we can see you and let you in if you come after the door closes.
================================================
New this week (Oct. 19)
This is week 7.
First part of HW3 available. Due on Thursday October 29.
================================================
New this week (Oct. 12)
This is week 6.
There will be no formal class, but a session devoted to the model in the first part
of the project on Tuesday, and a recitation session on Thursday, both by Ying.
================================================
New this week (Oct. 4)
This is week 5.
Please check the section called
Project, as it contains updated information.
Related material in the textbook is in Chapter 4.
I revised the first file on dual problems, download this one preferably!
new file
Information on the midterm and final exams has been updated.
Update on HW2:
The following problems are from the textbook.
Problem 3 is exercise 4.1 on p. 187.
Problem 4 is exercise 3.12 on p. 131.
Problem 5 is exercise 3.17 on p. 132.
Problem 6 is exercise 3.20 on p. 133.
The homework is due on Thursday 15 October at 3pm.
================================================
New this week (Sept. 28)
This is week 4.
Related material in the textbook is in Chapter 3.
================================================
New this week (Sept. 21)
This is week 3.
Please go to the slides from the "slides" section, they will be presented on a class-by-class basis, not here.
Homework 1 is available
here.
Related material in the textbook is in Chapters 1, 2 and 3.
You should have a look at the files in the
review folder.
New this week (Sept. 14)
This is week 2 .
Make sure that you download a demo version of "classic LINDO" from the LINDO website.
Please also download a demo version of GAMS from the gams website.
We will usually not use them, but they can be used as a backup, for you to check your understanding of the course material.
Slides from Bertsimas are available
here.
Take the habit to get the slides from the "slides" section where they will be presented on a class-by-class basis.
New this week (Sept. 10)
This is week 1 .
This is the first message for this semester.
The website is under construction, and in some way, it will be so until the end of the semester :)
Feel free to browse now, and during the semester, feel obliged to do so at least every second day,
as this will be the main communication channel from instructor/TA to you.
General Information on Homework and readings:
You are allowed, and even encouraged, to work in groups on the homework problems.
However, you must each return your own answer, and
it must be your own!
It is NOT allowed to use any outside help or outside source in this class without referencing it.
It is all right to cooperate with your classmates as long as you do not copy someone else's work.
The first readings for the semester are taken from the INFORMS Journal called Interfaces.
You can download them using the Penn Library journal access system (requires Pennkey).
The first reading emphasizes the usefulness of spreadsheets in Management Science/Operations Research.
Interfaces, Vol.38, No.4, July-August 2008, p. 225-227.
The second one presents an application of spreadsheet optimization for scheduling radiology residents at a teaching university hospital.
Interfaces, Vol.38, No.4, July-August 2008, p. 311-323.
These papers should be read by the end of next week.
While this course does not emphasize the use of spreadsheets, they are a useful tool, either alone or combined with a system such as GAMS.
As he stated it himself,
"Linear programming is a revolutionary development giving man the ability to state general objectives and to find, by means of the simplex method, optimal policy decisions for a broad class of practical problems of great complexity."
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.
or, click on for OR champions!
General Information
Excerpt from the first article quoted about G.B. Dantzig:
"Dr. Dantzig's seminal work allows the airline industry, for example, to schedule
crews and make fleet assignments. It's the tool that shipping companies use to
determine how many planes they need and where their delivery trucks should be
deployed. The oil industry long has used linear programming in refinery
planning, as it determines how much of its raw product should become different
grades of gasoline and how much should be used for petroleum-based byproducts.
It's used in manufacturing, revenue management, telecommunications, advertising,
architecture, circuit design and countless other areas."
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.
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.
You should download the academic demo version available on 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 download (and look at :o) )this
ppt file.
Office: 5th floor, OPIM Dept., JMHH
Phone: 215-898-8235
Email: guignard at wharton.upenn.edu
URL: http://opim.wharton.upenn.edu/~guignard
Office Hours: Wed., 4:30-6 pm, in one of the OPIM Conference rooms (5th floor, JMHH).
The TA for the class is Ying Liu.
Email: liuying1 at seas.upenn.edu
Office Hours: Monday, 4:30-6 pm, in one of the OPIM Conference rooms (5th floor, JMHH).
Office hours will start the week of September 21.
The teaching team can be reached at the following email address:
opim910 at yahoo.com
Textbook
"Introduction to Linear Optimization" by Dimitris Bertsimas and John N. Tsitsiklis,
ISBN-10: 1-886529-19-1
ISBN-13: 978-1-886529-19-9
Publication: 1997, 608 pages, hardcover
Price: $89.00.
Suggested additional reading:
"Introduction to Mathematical Programming," by W. L. Winston and M. Venkataramanan, Thomson, 4th edition.
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 2009 can be found
here.
It is a living creature and might evolve as time goes by.
Slides
In case I should forget to put a link to the slides for a particular class, you can always look for all slides
here.
Slides from Bertsimas
are available
here.
Class #1
first set of slides for this course.
Orlin's modified Chapter 1 slides, and the excel file
for optimization
Class #2
Gans' class 2 slides,
and
Orlin's class 2 slides
plus
lindo files
Class #3
from Bertsimas
and
from Orlin
plus
problem files
Class #4
end of last class
and
new file, both from Orlin
plus
problem file.
Class #5
end of class 2 , again,
and
file 1, end of last class, and
file 2 ,
new file, both from Orlin
plus
problem file.
Class #6
Continuation of class 5:
this file.
Class #7
New slides:
this file.
Class #8
New slides:
dual problems and
duality and complemetary slackness.
Additional readings:
what is the dual?
a dual example
an infinite duality gap
Class #9
New slides:
this file.
Classes #10 and 11
New slides:
this file.
Class 12
New slides:
this file.
Class 13
New slides:
this file.
Classes 14 and 15
New slides:
this file.
Class 16
New slides:
this file. Grading Policy
Class Summaries
For 2009:
Homework
Homework #1.
Homework #3, part 1.
Homework #3, part 2.
Homework #4, part 1.
Homework #4, part 2.
Homework #5, problem 1.
Homework #5, problem 2.
Homework #5, part 3.
Term Project
This year, the term project will be in two parts. Together, they will involve
working on two problems similar to those found in the INFORMS journal called Interfaces.
This will be an opportunity to study and work on broader, more realistic problems than
those found in the homework.
For copyright reasons, the project was sent to you by email.
As you must have seen by now, it is in two parts. Part one, to be done first, is meant
to give you a chance to check your formulation with the TA before you start working on Part 2,
just in case you have some mistake(s) in the model.
What you should do (with your group) is work out part 1 and write down your answers, then email the file to Ying
at the latest Monday evening October 12.
In class on Tuesday October 13, she will be available to discuss your formulation and will either
tell you that your formulation is fine and that you can go ahead with Part 2 without making any change,
or she will point out your mistake(s) in case you missed something to allow you to start Part 2 with a correct formulation.
No amswer sheet will be given because after you get Ying's green light,
you should continue the project using your own, possibly modified, formulation,
with your own notation and so on.
You should then complete Part 2 of the project by the end of Ocbober.
The second project will be on a problem that you identify. It would be especially
interesting if these projects could be based on optimization
problems arising on campus: dining, transportation, heating/cooling, recycling,
medical care, maintenance, scheduling, etc...
One-page proposals for these projects should be returned on Thursday 22 October
(notice the change of date, as I will be away the week of October 15). 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.
Groups will change so that you will work with different people for different projects.
Group assignments were sent to you by email already.
There will be a class presentation at the end of the semester,
and a written report, including the code(s) developed and the listings,
will be due at the time of the final exam.
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.
you can also look at the large collection of actual optimization projects descrived in the journal Interfaces. You could choose to work on a scaled down version of one of these real projects.Exams
Handouts
Interesting Links about Operations Research/Management Science
The University calendar for fall 2009.
Please read
Last Updated: University Policy on Religious Holidays