\documentclass{article}
\usepackage{latexsym}
\usepackage{amsfonts}
\newcommand{\R}{{\mathbb R}}
\begin{document}

\begin{center}
{\bf C\&O 370 \\ Deterministic OR Models \\ Winter 1996 \\}
\end{center}

\begin{flushleft}
\begin{tabular}{lll}
{\bf Instructors:} & (01) Dr. Charles E. Haff & (02) Dr. Henry Wolkowicz\\
 & ~~~~~~MC 5025, ext. 5594 & ~~~~~~MC 6065, ext. 5589 \\
 & ~~~~~~chaff@math & ~~~~~~henry@orion \\
& & \\
{\bf Tutors:} & Baoyan Ding & Qing Zhao \\
 & MC 5126, ext. 5260 & MC 5136A, ext. 5334 \\
 & bding@jeeves & qzhao@barrow \\
& & \\
{\bf Lectures:} & (01) 8:30 MWF, MC 4063 & \\
 & (02) 10-11:30 TR, MC 4060 & \\
\end{tabular}

\begin{tabular}{ll}
{\bf Texts:} & \underline{Applied Mathematical Programming}, Bradley, Hax
and Magnanti \\
 & \underline{GAMS, A User's Guide}, Brooke, Kendrick and Merraus. \\
& \\
{\bf References:} & \underline{Linear Programming}, Chv\'{a}tal \\
 & \underline{Intro. to Math. Programming}, Hillier \& Lieberman \\
 & \underline{Home Page, C\&O 370}, \\
 &
\underline{ftp://orion.uwaterloo.ca/pub/henry/teaching/w96/370.w96/readme.ht
ml}\\
& \\
{\bf Term Work:} & Term work will consist of \underline{homework problems},
\underline{case studies}\\
& and a \underline{research project}. \\
& See attached schedule of assignments, due dates and instructions. \\
& \\
{\bf Midterm Exam:} & A 2-hour exam, \underline{7-9}, on \underline{Friday,
March 1}, in \underline{MC 4020/MC
4021}.\\
& \\
{\bf Final Exam:} & A 3-hour exam, scheduled by the registrar.\\
& \\
{\bf Marking Scheme:} & Homework ~~~~~~~~~~10\%\\
                      & Case Studies ~~~~~~~20\%\\
                      & Research Project ~~20\%\\
                      & Midterm Exam ~~~~20\%\\
                      & Final Exam ~~~~~~~~~30\%
\end{tabular}
\end{flushleft}

\newpage
\begin{center}
{\bf C\&O 370 \\ HOMEWORK \\}
\end{center}

\vspace{.25in}
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 \underline{individually} and handed in for grading.

Some problems will be \underline{computational exercises} giving practice
with implementing general algorithms,
using available software, and others will be \underline{modelling
exercises} giving practice with extracting
precise mathematical formulations from applied problems.

\begin{center}
\begin{tabular}{ll}
\underline{Format for Computational Exercises} & \underline{Format for
Modelling Exercises}\\
& \\
$\bullet$ Problem Statement & $\bullet$ Problem Statement \\
$\bullet$ Solution Summary & $\bullet$ Solution Summary (if appropriate) \\
$\bullet$ Outline of Solution Method & $\bullet$ Model Development (see
section on Case Studies \\
 & ~~~for details)\\
& $\bullet$ Brief Model Critique
\end{tabular}
\end{center}

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.

The following pages give the homework assignments and their due dates.

\newpage
\begin{center}
{\bf C\&O 370}
\end{center}

\vspace{.25in}
\begin{flushleft}
{\bf
\underline{Homework \#1 (Linear Programming)}}

\vspace{.10in}
\underline{Due:} Monday (Tuesday), January 22 (23)

\vspace{.10in}
\underline{Reading}\\
~~~~~B/H/M, pp. 48-181 (LP/Sensitivity/Duality)\\
~~~~~B/H/M, pp. 690-703 (Revised Simplex Algorithm)\\
~~~~~Chv\'{a}tal, pp. 97-105 (Revised Simplex Algorithm)\\
~~~~~$\Box$ , FAQ on linear programming.

\vspace{.10in}
\underline{Problems}\\
~~~~~1.1 B/H/M, p. 33, \#5 \\
~~~~~1.2 B/H/M, pp. 46-47, \#28(b) \& (c) (see Chv\'{a}tal, pp. 213-227) \\
~~~~~1.3 B/H/M, pp. 136-137, \#14 \\
~~~~~1.4 B/H/M, pp. 193-194, \#6

\vspace{.50in}
{\bf
\underline{Homework \#2 (Network Programming)}}

\vspace{.10in}
\underline{Due:} Monday (Tuesday), February 12 (13)

\vspace{.10in}
\underline{Reading}\\
~~~~~B/H/M, pp. 310-326 (Network Models) \\
~~~~~Chv\'{a}tal, pp. 291-299 (Transshipment Problem) \\
~~~~~Chv\'{a}tal, pp. 367-378 (Maximum Flow Problem) \\
~~~~~$\Box$ , shortest path, maximum flow problems \\
~~~~~$\Box$ , information and software on network models \\
~~~~~$\Box$ , linear network optimization at NEOS

\vspace{.10in}
\underline{Problems}\\
~~~~~2.1 B/H/M, p. 354, \#8 \\
~~~~~2.2 B/H/M, p. 356, \#13 \\
~~~~~2.3 B/H/M, p. 359, \#19 \\
~~~~~2.4 Chv\'{a}tal, p. 388, \#22.9 \\

\newpage
{\bf
\underline{Homework \#3 (Mixed Integer Programming)}}

\vspace{.10in}
\underline{Due:} Monday (Tuesday), March 4 (5)

\vspace{.10in}
\underline{Reading}\\
~~~~~B/H/M, pp. 366-385 (MIP Models) \\
~~~~~B/H/M, pp. 402-407 (Cutting Planes) \\
~~~~~Chv\'{a}tal, pp.195-211 (Cutting Stock Problem) \\
~~~~~$\Box$ , systems analysis laboratory \\
~~~~~$\Box$ , optimization technology center \\

\vspace{.10in}
\underline{Problems}\\
~~~~~3.1 B/H/M, pp. 408-409, \#6 \\
~~~~~3.2 B/H/M, p. 496, \#16 \\
~~~~~3.3 B/H/M, p. 414, \#18 \\
~~~~~3.4 Chv\'{a}tal, pp. 211-212, \#13.3 \\

\vspace{.50in}
{\bf
\underline{Homework \#4 (Nonlinear Programming)}}

\vspace{.10in}
\underline{Due:} Monday (Tuesday), March 25 (26)

\vspace{.10in}
\underline{Reading}\\
~~~~~B/H/M, pp. 561-608 \\
~~~~~$\Box$ , FAQ on nonlinear programming \\
~~~~~$\Box$ , Introduction to Convex Optimization \\
~~~~~$\Box$ , Newton-Raphson Method

\vspace{.10in}
\underline{Problems}\\
~~~~~4.1 B/H/M, p. 608, \#2 \\
~~~~~4.2 B/H/M, p. 611, \#7 \\
~~~~~4.3 B/H/M, pp. 622-623, \#28 \\
~~~~~4.4 B/H/M, pp. 623-624, \#30
\end{flushleft}

\newpage
\begin{center}
{\bf C\&O 370 \\ CASE STUDIES \\}
\end{center}

\vspace{.25in}
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 \underline{formal reports}, as if done for a
``customer''.
They should be concise, clearly written and self-contained.

\begin{flushleft}
\underline{Format for Case Studies}
\end{flushleft}
\begin{itemize}
\item[-] Problem Statement
\item[-] Solution Summary
\item[-] Model
\begin{itemize}
\item Assumptions
\item Index Sets and Variables
\item Data
\item Program (objective function \& constraints, clearly expressed and
annotated)
\end{itemize}
\item[-] Assessment of Solution Validity
\item[-] Critique of Model Choice and Assumptions
\item[-]Appendices (e.g. GAMS Program \& Output)
\end{itemize}

Each Case Study should be done in \underline{groups of 2 or 3 students}.
These groups may be comprised of students from either of the two sections
of the course.

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.

The following pages give the Case Studies and their due dates.

\newpage
\begin{center}
{\bf C\&O 370}
\end{center}
\begin{flushleft}
\underline{Case Study \#1} (Due: Wednesday (Thursday), January 24 (25))
\end{flushleft}

An {\em Exgon} oil refinery produces four types of raw gasoline: alkylate,
catalytic-cracked, straight-run and isopentane.
Two important characteristics of each gasoline are performance number PN
(measuring
antiknock properties) and vapor pressure RVP (measuring volatility).
These characteristics, together with the production limits in barrels per
day, are
as follows:

\begin{center}
\begin{tabular}{lccc} \hline
 & PN & RVP & Production Limit \\ \hline
Alkylate & 107 & 5 & 3,814 \\
Catalytic-Cracked & 93 & 8 & 2,666 \\
Straight-Run & 87 & 4 & 4,016 \\
Isopentane & 108 & 21 & 1,300 \\ \hline
\end{tabular}
\end{center}
These gasolines can be sold either raw, at \$4.83 per barrel, or blended into
aviation gasolines (Avgas A and/or Avgas B).
Quality standards impose certain requirements on the aviation gasolines; these
requirements, together with the selling prices, are as follows:

\begin{center}
\begin{tabular}{lccc} \\ \hline
 & PN & RVP & Price per Barrel \\ \hline
Avgas A & at least 100 & at most 7 & \$6.45 \\
Avgas B & at least 91 & at most 7 & \$5.91 \\ \hline
\end{tabular}
\end{center}
The PN and RVP of each mixture are simply weighted averages of the PNs and
RVPs of
that mixture's constituents.
For example, if 1,000 barrels of Avgas A was a blend of 600,100,200 and 100
barrels
of Alkylate, Catalytic-Cracked, Straight-Run and Isopentane, respectively, then:
\[ \begin{array}{rcccr}
\mbox{PN (AvgasA)} & = & \displaystyle \frac{(600 \times 107) + (100 \times
93) + (200 \times
87) + (100
\times 108)}{1,000} & = & 101.7 \\
& & & & \\
\mbox{RVP (AvgasA)} & = & \displaystyle \frac{(600 \times 5) + (100 \times
8) + (200 \times 4) +
(100
\times 21)}{1,000} & = & 6.7
\end{array} \]
\begin{itemize}
\item[(a)]
Develop and solve a GAMS-like model by which {\em Exgon} can realize a
maximum daily sales
revenue from this refinery.
\item[(b)]
Write down the dual of your model from (a), and state the units of the dual
variables corresponding to the production-limit constraints.
\item[(c)]
Another oil company has offered to sell additional quantities of the four raw
gasoline types to {\em Exgon} at specified prices.
Analyze how {\em Exgon} should assess their offer.
Illustrate your analysis numerically by choosing the specified prices and
{\em Exgon's} profit margins.
\end{itemize}

\newpage
\begin{center}
{\bf C\&O 370}
\end{center}
\begin{flushleft}
\underline{Case Study \#2} (Due: Wednesday (Thursday), February 14 (15))
\end{flushleft}

A university has three professors who each teach four courses per year.
Each year four sections each of marketing, finance, and production must be
offered.
At least one section of each of these three courses must be offered in each
of the
Fall and Spring terms.
Each professor's preferences for courses and teaching terms are given in Table 1
below.

\begin{center}
\begin{tabular}{lccc}
 & Professor 1 & Professor 2 & Professor 3 \\ \hline
Fall preference & 3 & 5 & 4 \\
Spring preference & 4 & 3 & 4 \\
& & & \\
Marketing preference & 6 & 4 & 5 \\
Finance preference & 5 & 6 & 4 \\
Production preference & 4 & 5 & 6 \\ \hline
\end{tabular}
\end{center}
\begin{center}
{\bf Table 1.  Preference Data}
\end{center}
The total satisfaction a professor earns teaching a course is the sum of
the term
preference number and course preference number.

Develop and solve a GAMS-like model by which the dean can assign professors
to courses so that
the total satisfaction of the three professors is a maximum.
Include a carefully drawn and labelled network upon which your model is based.

\newpage
\begin{center}
{\bf C\&O 370}
\end{center}
\begin{flushleft}
\underline{Case Study \#3} (Due: Wednesday (Thursday), March 6 (7))
\end{flushleft}

In women's gymnastics competition there are four events: vault, uneven
bars, balance beam and floor exercise.
Each team can enter up to six gymnasts in each of these events.
Only the top five scores from the six entrants in each event are included
in the team score.
A major constraint in selecting the six entrants for each event is that
there must be at least four
``all-arounders'' who must compete in all four events.

Develop and solve a model for assisting the coach in selecting the entrants
for each event so as to maximize the
expected total team score.
Test your model using the following data:

\begin{center}
\begin{tabular}{ccccc}
\multicolumn{5}{c}{\bf Events}\\
Gymnast & Vault & Bars & Beam & Floor \\
1 & 9.80 & 9.10 & 9.15 & 8.90 \\
2 & 9.00 & 8.90 & 9.10 & 8.50 \\
3 & 8.50 & 8.30 & 9.20 & 9.00 \\
4 & 7.00 & 9.00 & 8.30 & 8.65 \\
5 & 9.40 & 8.30 & 9.00 & 8.50 \\
6 & 8.90 & 8.80 & 7.90 & 9.00 \\
7 & 8.50 & 8.90 & 8.80 & 8.10 \\
8 & 9.10 & 9.20 & 8.50 & 8.20 \\
9 & 7.90 & 7.30 & 8.00 & 8.80 \\
10 & 8.90 & 8.80 & 9.10 & 8.70 \\ \hline
\end{tabular}
\end{center}
\begin{center}
Table:  Scores (0 to 10 in each event)  Expected by the Coach for each
Gymnast in each Event.
\end{center}

Additionally, the coach would like to know the second best and third best
solutions to this problem.

\vspace{.50in}
\begin{flushleft}
\underline{Case Study \#4} (Due: Wednesday (Thursday), March 27 (28))
\end{flushleft}

Do problem \#24, pp. 619-620 of B/H/M.

\newpage
\begin{center}
{\large\bf C\&O 370 \\ RESEARCH PROJECTS \\}
\end{center}

\vspace{.25in}
\noindent
{\bf General:}  In groups of three or less, you are to solve one of the
attached problems.
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 \underline{limited} technical
help.
Projects should be clearly written self-contained reports with the
narrative parts typed in English.

\vspace{.10in}
\noindent
{\bf Guidelines:}  The project problems tend to be open-ended and are
unlikely to have unique solutions.
It is a good idea to solve completely a restricted, or \underline{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
\underline{extensions}, obtained by relaxing the assumptions.

\noindent
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.

\vspace{.10in}
\noindent
{\bf 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:

\vspace{.10in}
\noindent
title page/table of contents/abstract/summary of results/main
body/references/appendices.

\vspace{.10in}
\noindent
The \underline{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.

\noindent
The \underline{main body} should contain your model(s), clearly developed
and annotated, your core problem analysis,
your extensions and avenues for further study.
Divide the main body into subsections as appropriate.

\noindent
\underline{References} (not a bibliography) are associated with the
citations in the text.
Include books, papers, software and personal consultations.

\noindent
\underline{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.

\noindent
Include, as a separate enclosure, a \underline{reproduction} of
presentation materials which you would use for a 15
minute oral presentation of your work.

\noindent
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.

\vspace{.10in}
{\bf Project Due Date:}  Monday (Tuesday), March 18 (19), in class.

{\bf Presentation Dates:}  Monday, March 25 through Friday, March 29.

\newpage
\begin{center}
{\bf C\&O 370 \\
RESEARCH PROJECTS \\}
\end{center}

\vspace{.25in}
\begin{itemize}
\item[1.]
\underline{Aluacha Balaclava College} \\
(see pages 16 and 17)

\item[2.]
\underline{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.

\noindent
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.

\item[3.]
\underline{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.

\noindent
The \underline{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.

\noindent
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.

\newpage
\item[4.]
\underline{File Transfers}\\
In your company, information is shared among departments on a daily basis.
This information includes the previous day's sales statistics and current
production guidance.
It is important to get this information out as quicly as possible.

\noindent
Suppose a communications network is to be used to transfer blocks of data
(files) from one
computer to another.
As an example, consider the following graph model:

\vspace{2.50in}
\begin{center}
{\bf Figure 1.}  Example of a file transfer network.
\end{center}

\vspace{5mm}
\noindent
Vertices $V_{1}, V_{2}, \ldots , V_{m}$ represents computers, edges $e_{1},
e_{2}, \ldots ,
e_{n}$ represents files to be transferred (between computers represented by
edge endpoints).
$T(e_{x})$ is the time it takes to transfer file $e_{x}$ and $C(V_{y})$ is
the capacity of the
computer represnted by $V_{y}$ to simultaneously transfer files.
A file transfer involves the engagement of both computers for the entire
time it takes to
transfer the file.
$C(V_{y})=1$ ;means that computer $V_{y}$ can only be involved in one
transfer at a time.

\noindent
We are interested in scheduling the transfers in an optimal way to minimize
the total time it
takes to complete them all.
This minimum total time is called the {\em makespan.}

\noindent
Your corporation has 28 departments.
Each department has a computer, each of which is represented by a vertex in
Figure 2.
Each day, 27 files must be transferred, represented by the edges in Figure 2.
For this network, $T(e_{x})=1$ and $C(V_{y}) = 1$ for all $x$ and $y$.
Find an optimal schedule and the makespan for the given network.

\newpage
$~~~~~$
\vspace{4.50in}
\begin{center}
{\bf Figure 2.} Network for your corporation.
\end{center}

Find an optimal schedule and the makespan for the same network but with the
following transfer
times:

\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline
$x =$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline
$T(e_{x})$ & 3.0 & 4.1 & 4.0 & 7.0 & 1.0 & 8.0 & 3.2 & 2.4 & 5.0 & 8.0 &
1.0 & 4.4 & 9.0 & 3.2
\\ \hline\hline
$x =$ & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & \\
\hline
$T(e_{x})$ & 2.1 & 8.0 & 3.6 & 4.5 & 7.0 & 7.0 & 9.0 & 4.2 & 4.4 & 5.0 &
7.0 & 9.0 & 1.2 & \\
\hline
\end{tabular}
\end{center}

\item[5.]
\underline{Loading Flat Cars}\\
Railroad flat cars are to be loaded with seven types of packing crates.
The crates have the same width and height but varying thickness ($t$, in
cm) and weight ($w$, in kg).
The table gives, for each crate, the thickness, weight and number available.
Each car has 10.2 meters of length available for packing the crates (like
slices of toast) and can carry up to 40
metric tons.
There is a special constraint on the total number of $C_5, C_6, C_7$ crates
because of a subsequent local trucking
restriction: the total space (thickness) occupied by these crates must not
exceed 302.7 cm per flatcar.
Additionally, at most 4 crate types may be loaded on any flatcar.

\begin{center}
\begin{tabular}{ccccccccc}
 & $C_1$ & $C_2$ & $C_3$ & $C_4$ & $C_5$ & $C_6$ & $C_7$ & \\
&&&&&&&&\\
$t$ & 48.7 & 52.0 & 61.3 & 72.0 & 48.7 & 52.0 & 64.0 & cm \\
&&&&&&&&\\
$w$ & 2000 & 3000 & 1000 & 500 & 4000 & 2000 & 1000 & kg \\
&&&&&&&&\\
 & 16 & 14 & 18 & 12 & 12 & 8 & 16 &
\end{tabular}
\end{center}

\vspace{3.50in}

\item[6.]
\underline{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 {\bf 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 {\bf Brick
Brewery} and determine in what ways its
production-inventory schedule might be improved.
\end{itemize}
\end{document}







