Marking Scheme:
-
Homework............ 10%
-
Case Studies........ 15%
-
Research Project.... 25%
-
Midterm Exam........ 20%
-
Final Exam.......... 30%
- Major Topics
- Sub-topics
- 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)
-
Introduction to Operations Research
-
Modeling Linear Programs (Chapter 2)
-
Related Resources:
-
Linear Programming, LP, Review
-
The Revised Simplex Method
( Chapter 7)
-
Duality ( Chapter 4)
-
Emphasis on Sensitivity Analysis ( Chapter 7.7)
- Related Resources:
-
Network Programming
-
Network Flow Problems, Models of Production & Transportation
(shortest path, maximum flow problems).
Please see the
Tutorial on Network Optimization, by Girard Cornuijols and Michael
A. Trick, Carnegie Mellon University.
A directory of files for the tutorial is
available locally.
Please see the file networks.txt.gz first to see which node goes with
which topic.)
(Also,
they are available in the course account
/u3/co370
in the public_html directory on undergrad.math.)
-
Sensitivity Analysis (Chapter 6.8)
-
Related Resources:
-
Integer Programming (Chapters 9,10,11)
-
Binary Variables, logistical equations
-
Cutting Planes, Branch and Bound
-
Related Resources:
-
Dynamic Programming (Topics from Chapter 12)
-
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: Thursday, Jan. 21
Reading
- M, pp. 1-134 (Modelling/Lin. Alg. Review)
Problems
- text Page 53, # 2.7.
- text Page 54, # 2.9.
- text Page 137, # 3.13,3.14,3.15.
-
Homework #2 (Duality-Practice)
Due: Thursday Feb. 11
Reading
- M, pp. 140-162, 227-264 (Duality, Optimality Conditions, Simplex
Method)
Problems
- text Page 265, # 7.3. Try and use the
diet problem at the optimization technology center.
- text Page 267, # 7.5.
- text Page 268, # 7.7-8. (You may find GAMS with CPLEX helpful.)
-
Homework #3 (Network Programming)
Due: Thursday Mar. 4.
Reading
-
text Chapters 9 and 10.
-
A Tutorial on Network Optimization, by Girard Cornuijols and Michael
A. Trick, Carnegie Mellon University.
To help with time delays, a directory
of files for the tutorial is
available locally.
(Also,
they are available in the course account
/u3/co370
in the public_html directory on undergrad.math.)
Problems
-
Homework #4 (Mixed Integer Programming)
Due: Thursday Mar. 18.
Reading
Problems (done by hand)
- text Page 346, # 9.44 (network).
- text Page 403, # 10.5 (knapsack B. and B.)
- text Page 408, # 10.11 (B. and B.)
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 self-contained.
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.
-
Crude Oil Production, text Page 73, Problem 2.43.
(Due: Tuesday, Feb 2)
-
Assigning Students to Field Study Projects, text Page 336, Problem
9.32.
(Due: Tuesday, Mar. 2)
General:
In groups of three or less, you are to solve one of the
attached problems. You must
before the first case
study is due.
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 self-contained reports with the
narrative parts typed in English.
Guidelines: The project problems tend to be real-world,
open-ended 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.
Presentation
Each group will give a 15-20 minute presentation in class on their
project.
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: Tues. Mar. 23, in class.
Presentation Dates: Thurs. Mar. 25 to Thurs. Apr. 1.
-
Ellipsoidal Approximations
Study and solve the following geometrical problems:
-
Outer Ellipsoid:
-
Find the ellipsoid of minimal volume that contains p given points in
n-dimensional Euclidean space.
-
Find the ellipsoid of minimal volume that contains p given ellipsoids in
n-dimensional Euclidean space.
-
Inner Ellipsoid:
-
Find the ellipsoid of maximal volume contained in a given polytope in
n-dimensional Euclidean space.
-
Find the ellipsoid of maximal volume contained in the intersection of
p given ellipsoids in
n-dimensional Euclidean space.
(Use random data to construct ellipsoids.)
References:
-
Both Kitchener and Cambridge Public Transit companies must assign bus
drivers and determine work shift schedules to accommadate given run
schedules while meeting the conditions of driver union contracts.
Using a subset of at least eight different bus runs, develop a model
for
assigning bus drivers to cover these runs while minimizing total
personnel costs.
-
A Bank Account Location Problem
A business firm has clients in cities i=1 to m,
and can maintain bank
accounts at locations j=1 to n.
When the payment for a client is mailed
by a check, there is usually some time lag before the check is cashed
(time for the mail to reach back and forth), in that time the firm
continues to collect interest on that money. Depending on the volume of
business in city i, and the time it takes for mail to go
between city i and location j, one can estimate the
float = expected benefit sij in the form of this
interest if clients in city i are paid by checks drawn out of
a bank account in location j, for i=1 to m,
and j=1 to n. The following data is given.
-
cj = cost in money units for maintaining a
bank account in location j, per year
-
sij = total float (=expected benefit in the form of
interest on money between the time a check for it is mailed, and the
time that check is cashed) per year, if payments due for customers in
city i are mailed in the form of checks drawn out of a bank
account in location j,.
-
N= upper bound on the total number of bank accounts that the
firm is
willing to maintain.
Determine the subset of locations where bank accounts should be
maintained and the bank accounts through which customers in each city
should be paid. (Use test data with e.g. m=7, n=5, N=3.
Contacting a local bank would be helpful.)
-
Vehicle Loading
-
Given a parking lot full of vehicles, it is required
to load them onto rail cars for shipment to car dealers.
The vehicles are grouped by destination on the
lot. Usually it is desired to ship the vehicles that have been on the lot
the longest first.
-
The rail cars are such that they can load 2 or 3 levels of vehicle
(depending on type of railcar). Larger vehicles can only be loaded to
bi-level railcars.
-
Often there are exceptions to the loading
requirement which would require a different set of cars
to be loaded first.
-
Sometimes cars have to be first unloaded from the rail cars, i.e.
their are inbound shipments as well as outbound.
-
The inputs to the algorithm are the curent inventory of vehicles and rail
types. The output is a set of vehicle movements resulting in the loading of
the rail cars prior to the scheduled departure of the train. An
objective function would be to minimize the loading time.
Possible questions and assumptions:
-
Does each group of cars have a clear lane to the loading ramp, or is
shifting vehicles to get at particular groups an issue?
-
Does the load factor vary? Typically a bi-level will load 10 and a
tri-level 16.
-
What type of exceptions, and how are the vehicles grouped or
identified?
-
Does unloading arriving vehicles
clog the ramp? Is part of the decision problem to identify
their storage location on the ramp?
-
Truck Scheduling
A division of an international trucking firm provides emergency freight
services with a fleet of over 200 trucks covering a geographic area east of
the Mississipi in the U.S. and Ontario and Quebec in Canada.
Their problem is to provide a level of service (response time) to
customers within this large service area. They want to get a vehicle (power
unit) to a customer's site within 90 minutes. Considering the time it takes
to get a vehicle moving, etc., this usually means they need a vehicle to be
within 60 miles of a customer when the emergency call is fielded.
The company would like to set up "service centers" that could
be anything where a truck (or set of trucks) could hang out. These service
centers (they could be truck stops, donut shops, etc...) would be located
such that a large number of the shipments (loads, pick ups) could be handled
within the 90 minute pick up tolerance level.
Construct a network where
the nodes would be the "service
centers" and the arcs would be the roads used to connect the "service
centers". The weighting on the nodes would be the number of loads (pick ups)
expected in a certain timeframe (i.e. within the next 12 hours). The
weighting on the links would be the number of times we travel between the
adjacent nodes. There might be two weightings on the links - since they
should probably be bi-directional.
Assume that several years worth of trip experience is known.
(Use fictitious data.)
Find the best placement for their trucks
so that customer service (time to respond to an
emergency pick up) is minimized; running trucks empty is minimized; and
turn downs (cannot take a load because we don't have the right truck in
the service center) is minimized. In short, find a way to
optimally position the fleet of trucks.
Some other points to consider:
- Assume orders arrive randomly in time.
- All vehicles are equipped with satellite tracking and communication
devices so they can begin the repositioning of a vehicle relatively quickly.
- All vehicles must adhere to the legal driving time regulations - which
may impact their ability to reposition quickly.
- Vehicles travel at 45 mph on average.
- Vehicles are 6 different types - minivan, cargo van, 1-ton, 3-ton, 5-ton
and tractor trailer. Demand and supply for each vehicle size needs to be in
the optimization equation.
- Most of the time there is one load per vehicle.
- To move a truck empty costs 50 cents a mile. A truck under load is
generating revenue. They want to minimize empty mile costs.
-
Designing a University Campus
Suppose that a new university is to be built on a given parcel of land.
After some preliminary analysis, certain fixed
locations are chosen for the buildings. Decide which buildings
should go into which locations. You should take into account
the cost of the building and the flow (people) between different
buildings. (As a possible scenario, pick U. of W. and decide
if the buildings can be relocated in a more optimal way.)
-
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
production-inventory schedule might be improved.
(In particular, Schneider's in Kitchener has an interesting "optimal
mixing" problem.)