"An applicationsoriented course that illustrates how various
mathematical models and
methods of optimization can be used to solve problems arising in
business, industry and
science"
Instructor:
Professor Henry Wolkowicz,
MC 6065, ext. 5589, henry@orion.math.uwaterloo.ca
Tutors:

Kevin Cheung , MC 5168, x6427, kkhcheung@barrow
Office Hours:

Henry Wolkowicz, MC6065: M 12:301:30, R 34

TA: Kevin Cheung MC 5168, W 1112
Lectures:
Texts:

Applied Mathematical Programming, Bradley, Hax and Magnanti
Please send me any
typos you find in the text.

GAMS, A User's Guide, Brooke, Kendrick and Merraus
(A copy for fall/98 is on reserve at the Davis Library UWU1538. )
This and the solver guide are now available online from the
GAMS homepage
References:

Linear Programming, Chvatal

Intro. to Math. Programming, Hillier & Lieberman

Home Page, C&O 370,
http://orion.uwaterloo.ca/~hwolkowi/henry/teaching/f98/370.f98/readme.html
Term Work:
will consist of homework problems, case studies,
and a research project.
(See attached schedule of assignments, due dates and instructions.)
Solutions can be obtained from the instructor and/or the TAs.
(Solutions for fall/98 are on reserve at the Davis Library UWU1539. )
Midterm Exam:
2hour exam, 79PM, Friday, Nov 6, 1998, in MC 4041
(in case of conflicts the time will be 57PM in MC 4064)
Final Exam:
A 3hour exam, scheduled by the registrar.
Marking Scheme:

Homework............ 10%

Case Studies........ 15%

Research Project.... 25%

Midterm Exam........ 20%

Final Exam.......... 30%
 Major Topics
 Subtopics
 Resources
for the different topics are included. (These are included for your
interest. You are not responsible for these topics for the exams or
assignments. However, I hope they are useful aids for you.)

Mathematical Programming ( Chapter 1)

Linear Programming, LP, Review

The Revised Simplex Method
( Chapter 2 & Appendices A & B)

Duality ( Chapter 4: 4.14.6 and 4.8)

Emphasis on Sensitivity Analysis ( Chapter 3)
 Cutting Stock Problem: An exercise in the revised simplex method and
sensitivity analysis. (Section 12.8)
 Related Resources:

Network Programming ( Topics from Chapter 8)

Models of Production & Transportation

Network Flow Problems

Sensitivity Analysis

Related Resources:

Integer Programming ( Sections 9.19.4)

Binary Variables, logistical equations

Cutting Planes, Branch and Bound

Related Resources:

Dynamic Programming ( Topics from Chapter 11)

Models of Replacement & Allocation

Path Problems & Recursive Computation

Related Resources:
There will be 4 homework assignments given throughout the term.
Each will consist of problems and specified readings from the text,
references and resource materials listed on the
C&O 370 homepage.
The problems are to be done individually and handed in for grading.
Some problems will be computational exercises giving practice
with implementing general algorithms,
using available software; and others will be modelling
exercises giving practice with extracting
precise mathematical formulations from applied problems.
 Format for Computational Exercises:
 Problem Statement
 Solution Summary
 Outline of Solution Method

Format for Modelling Exercises:
 Problem Statement
 Solution Summary (if appropriate)
 Model Development (see section on Case Studies for details)
 Brief Model Critique
The T.A.'s will mark a subset of the problems and will hold office hours to
help resolve any difficulties you may
have.
The 10% contribution of homework to your course grade belies its
importance, as both exams will be based upon
homework readings and problems.
According to my calculations, the problem
doesn't exist.

Homework #1 (Linear Programming)
Due: Tuesday, Sept. 29.
Reading
Problems
 B/H/M, pp. 39, #17 (LP/Modelling)
 B/H/M, pp 45, #25 (cutting stock model).

(simplex method)
Consider the LP:
max cx s.t. Ax <= b, Bx=d, l<=x<=u,
where (using matlab notation  ; denotes a new row)
c=[5,2,3,3,6,1],
A=[3, 1, 4, 2, 5, 1;5, 4, 2, 3, 2, 3], b=[3;25]
B=[1,1,2,1,1,2], d=4, l=[0,2,infinity,3]
u=[infinity,10,0,3].
Variables 5,6 are unconstrained.
Please solve the problem using GAMS or the
Optimization Technology Center facility.
Please show the basic feasible solution for each iteration.
(GAMS will be the main tool that you will need for the final project.
Here are
one and
two sample GAMS files that use the LP model.)
 B/H/M, pp 148152 #26 (sensitivity analysis).

marker comments on assignment 1

Homework #2 (DualityPractice)
Due: Thursday, Oct. 22.
Reading
 B/H/M, pp. 157229 (DualityPractice)
Problems

Homework #??? (Network Programming)
Due: not this semester!! But please do the reading!!
Reading
 B/H/M, pp. 310337 (Network Models)
Problems

Homework #3 (Mixed Integer and Dynamic Programming)
Due: Tuesday, Nov. 24.
Reading
 B/H/M, pp. 366385 (MIP Models)
 B/H/M, pp. 385407 (Cutting Planes and Branch and Bound)
 B/H/M, pp. 453466 (Dynamic Programming)
Problems
 B/H/M, pp. 408 #6 (MIP Models)
 B/H/M, pp. 411 #13 (Branch and Bound and Implicit Enumeration)
 B/H/M, pp. 415 #19 (Cuttting Planes)
Case Studies are definitive problems requiring a greater degree of analysis
and thoroughness of presentation than do
homework problems.
Generally, computer software such as GAMS will be a required component of
such problems.
Case Studies should be formal reports, as if done for a
customer.
They should be concise, clearly written and selfcontained.
Format for Case Studies
 Problem Statement
 Solution Summary
 Model
 Assumptions
 Index Sets and Variables
 Data
 Program (objective function & constraints, clearly expressed and
annotated)
 Assessment of Solution Validity
 Critique of Model Choice and Assumptions
 Appendices (e.g. GAMS Program & Output)
Each Case Study should be done in groups of 2 or 3 students.
On the given due dates each group should submit one paper only, with each
group member's name, I.D. and course
section number on the title page.
Each case study will be graded and returned to you.
The grading will be based upon both technical accuracy and clarity of
presentation.
It is imperative that you stretch your communication skills.
Project and Case Evaluation Scheme.

Diet Problem, BHM Pages 1934 #6
(Due: Thursday, Oct. 15.)

B/H/M, pp 148152 #26 (sensitivity analysis from assignment 1)
(Due: Thursday, Nov. 5  I will accept this until Monday noon Nov 8.)
 Write a GAMS program to solve this problem from the text. Please
model it appropriately in GAMS, e.g. selfdocumentation.

Add some constraints to the problem to help management solve certain
problems. Illustrate how GAMS can be used to quickly make changes in
your model.
Be inventive. For example: suppose that some of the variables
are restricted to be integers; add a logical constraint on the inventory
such as no teflon cannot be stored unless a certain amount of plastic is
stored; etc...

Here is a
a local copy of the Oct/98 version of the
annotated bibliography on sensitivity analysis for MIP
maintained by Harvey Greenberg.
General:
In groups of three or less, you are to solve one of the
attached problems. You must
inform your instructor about your project choices
before the first case study is due. Please decide on a first, second,
and third choice.
You may use any resources as aids, provided you reference them carefully.
You may consult with instructors/tutors concerning your planned approach
and to obtain limited technical help.
Projects should be clearly written selfcontained reports with the
narrative parts typed in English.
Guidelines: The project problems tend to be realworld,
openended and are unlikely to have unique solutions.
It is a good idea to solve completely a restricted, or core,
version of your problem by making
appropriate simplifying assumptions and then to do what you can with each
of a progression of harder versions, or
extensions, obtained by relaxing the assumptions.
Your project will be assessed primarily in terms of how well you
communicate your knowledge of both the problem and
your model.
Accordingly, make your analysis as thorough as possible, and make certain
that your model is an appropriate one. Your attitude should be one of an
employee of a company or a consultant working for a company.
Data:
In many instances you are not given specific data for the problem. In
this case, please make up your own data.
Format: The format should be similar to that of the case studies,
with the added components of a detailed
model critique and analyses of core problem extensions.
The report structure should include:
title page/table of contents/abstract/summary of results/mainbody/references/appendices.
The summary of results should offer motivation for the reader
to want to read the rest of the report.
It begins on a separate page (following the abstract), which is page number 1.
The main body should contain: your model(s); clearly developed
and annotated; your core problem analysis; your model and solution critique;
and your extensions and avenues for further study.
Divide the main body into subsections as appropriate.
In addition, your critique can include a comparison with a manual
(intuitive or other)
solution of the problem, thus illustrating the strength of the model.
References (not a bibliography) are associated with the
citations in the text.
Include books, papers, software and personal consultations.
Please ensure that all references are included. Due to the ease with
which related work can be found on the internet, it is important that
you include references to all work that you have used.
Appendices should be used for such things as extended
background material, programmed versions of your
model(s) and output and any kind of lengthy detail that would interfere
with the flow of text.
Include, as a separate enclosure, a reproduction of
presentation materials which you would use for a 1520
minute oral presentation of your work.
Well in advance of the project due date arrange a meeting with your
professor to discuss your overall study plan,
your choice of model(s) and the resources which you anticipate using.
Project Due Date: (Thursday, Nov. 19 originally) postponed till Tuesday
Nov. 24 in class.
Presentation Dates: Nov. 26Dec 3.
student groups and choices

Ellipsoidal Approximations
Study and solve the following geometrical problems:

Outer Ellipsoid:

Find the ellipsoid of minimal volume that contains p given points in
ndimensional Euclidean space.

Find the ellipsoid of minimal volume that contains p given ellipsoids in
ndimensional Euclidean space.

Inner Ellipsoid:

Find the ellipsoid of maximal volume contained in a given polytope in
ndimensional Euclidean space.

Find the ellipsoid of maximal volume contained in the intersection of
p given ellipsoids in
ndimensional Euclidean space.
(Use random data to construct ellipsoids.)
References:

Aircraft Rerouting
Suppose that you are given 18 aircraft and 68 legs.
(A leg is one piece of the aircraft route, e.g. one aircraft may fly 3
legs as its route: 1. MontrealToronto, 2. TorontoChicago, 3
ChicagoL.A.)
 Find the best aircraft routing.
 Then suppose that you have to delete 8
legs. Find the best aircraft rerouting.
(Use your own data. You can see a
small example of a routing problem in the file crewschd.gms.gz in
the miscfiles directory.
You can also use the following
real world data from Delta Airlines
(courtesy of Qing Zhao at Delta.)
)

Some paper mills receive orders for paper rolls with relatively large
widths compared with a master reel to be cut into the ordered sizes. For
example, when all ordered sizes exceed half the widtho fthe master reel,
the trim results are disastrous.
Skiving assumes that, along with finished rolls, several auxiliary rolls
will be cut from a amaster reel. The auxiliary rolls will be skived
together to form finished rolls of the require sizes.
(reference
pp. 472483 in
Volume 39, Number 3 in
SIAM Review.)

Solve a standard cutting stock problem using LP and approximation
techniques. (Use your own data.)

Create some data that would be appropriate for the skiving technology
and solve it. (The sample data in the article, page 480, can be modified.)

Snow Removal
After a snowfall, three snowplows are dispatched to the Old Beechwood
area
of Waterloo.
All streets in that area must be plowed twice, one in each direction, in
order to remove all of the snow.
Develp and solve a model for determining how the three plows should be
used
in order to finish all plowing in the
minimum amount of time.

Oil Lease Problem
An oil company has shown an interest in an oil field containing several
potential oil wells.
The dollar value of each well is assumed known based upon estimated
production.
A plot of land of known dimensions containing each well must be leased
by
the company if the well is selected.
The plots of land associated with various sets of wells may overlap.
There is a major road running parallel to the southern boundary of the
oil
field, and a side road must be built
joining any selected well to this major road.
The net value of any set of selected wells is the sum of the
values of the wells minus the land lease
and side road construction costs.
Develop a model by which the oil company can select a set of wells of
maximum net value.
Illustrate your model numerically using parameter values of your choice.

Operational Analysis
Select a local business, and determine in what ways it might benefit
from some sort of operational analysis.
For example, one might select a business such as Domino's Pizza
and determine in what ways its delivery policy
might be made more profitable.
Alternatively, one might select a manufacturing business such as
Brick Brewery and determine in what ways its
productioninventory schedule might be improved.
(In particular, Schneider's in Kitchener has an interesting "optimal
mixing" problem.)