http://www.student.math.uwaterloo.ca/~co351/
EMAIL: course_number AT student DOT math DOT uwaterloo DOT ca
-
Overview:
-
CO351 is an introductory course on Network Flows,
covering some of the theory, algorithms, and applications.
Networks are pervasive in everyday life:
road-networks connect cities,
electrical and phone networks connect homes,
social networks connect friends, etc.
The course focuses on optimization problems on networks.
A familiar example is the shortest paths problem:
What is the shortest route between cities A and B in a road-network?
Almost all of the problems of interest can be formulated
as linear programming problems (LPs);
moreover, these LPs have special properties
useful for designing algorithms
and for proving theoretical results.
Topics include:
Transshipment problems (TP).
Shortest path problems.
The max-flow min-cut theorem and applications.
Minimum cost flow problems.
Network simplex and primal-dual algorithms.
Applications in transportation, distribution, project planning, assignments, etc.
Prereq: (One of CO 250/350 or 352 or 355 or CM 340) and MATH 239 or
249. Not open to General Mathematics students.
-
Time & Place:
-
1:30-2:20 MWF MC4063
-
Office hours:
-
Instructor
J.Cheriyan MC 6067 phone x35591 Tue 1:30-3:00 (Nov.2 onwards)
Teaching Assistants:
R.Kapadia DC 3144 phone x37814 Thu 1:00-2:00 (starting Sep.30)
Network Flow Theory - C&O 351.
May be purchased from Pixel Planet, MC2018, ext.35997.
Final 55%
Midterm 30% (or, Project 30%)
Assignments 15%
Students may opt for a course project, instead of writing the midterm exam.
Projects are OPTIONAL.
To pass the course, a pass in the final exam is required.
Please look up UW ACE for info on the Midterm Exam,
which is on Oct.20
(UW ACE)
The midterm exam is on October 20, Wednesday.
There are two sessions,
5:00-7:00pm in MC 4042 OR
7:00-9:00pm in MC 4045 .
You may write in either one of the sessions, but those writing in the
5:00-7:00 session cannot leave the exam hall until 7:00pm.
Usually, it is much easier to explain math in person
rather than over email.
Students are welcome to ask questions in class, or just after class,
or during office hours.
Also, if necessary, students may ask instructor/TAs to schedule
meetings outside regular office hours.
If email is essential (e.g., if you are away from town, or you wish to
schedule an appointment), then send email to the course account:
course_number (5 letters, starts with co) AT student DOT math
Assignments will be posted on this website every 1-2 weeks.
All the assignments are REQUIRED (see the policy on INC requests, at
the bottom of this page).
Assignment solutions should be handed in at the start of class on the
due date.
There is a penalty on late submissions.
Acknowledge all outside help and collaboration in the submission
(no need to mention help from instructor/TA or from course material).
Assignment 1
(look it up on UW ACE) , due Mon. Sep. 20
Note for (Q2):
part(d), optional part, needs a change:
please replace "D has no cycle" by "D has no cycle or dicycle"
Assignments 2 -- 8
(look it up on UW ACE)
Below is a TENTATIVE schedule for the assignments;
some dates may have to be changed due to unforeseen events.
| Schedule for Assignments (Tentative) |
Ass. No. |
Posting Date |
Submission Date |
Chapters Covered |
| #1 |
Sep.13 |
Sep.20(Mon) |
CO350 Review, 1 |
| #2 |
Sep.20 |
Sep.27(Mon) |
1, TPs |
| #3 |
Sep.27 |
Oct.4(Mon) |
TPs, 2 |
| #4 |
Oct.4 |
Oct.13(Wed) |
TPs, 2 |
| #5 |
Oct.20 |
Nov.1(Mon) |
2, 3 |
| #6 |
Nov.1 |
Nov.10(Wed) |
3 |
| #7 |
Nov.10 |
Nov.19(Fri) |
3 |
| #8 |
Nov.24 |
Dec.1(Wed) |
4 |
| #9 |
Dec.6 |
Not for submission |
TBA |
Late assignments will not be graded.
A missed midterm exam, or a missed or late assignment
will be treated the same as a mark of zero unless the cause is
illness (medical note required), or
similar good reason given promptly in writing,
in which case the corresponding weight will
be transferred to the final exam.
In case of a missed final exam, the course policy on INC requests
shall apply; see below.
Info on AMPL and its use from the CO370 Fall'10 web page.
Frequently Asked Questions about AMPL
Input files for AMPL for a small example of TP (transshipment problem)
with 5 nodes.
The MODEL file for the TP,
the DATA file for the TP .
Note that the "costs matrix" assigns costs to
all 5 X 5 entries of the matrix, but only 8 of these entries are
relevant, since the other entries of 100 represent infinite costs;
the diagonal entries are zero.
The model was solved on the NEOS server, using
this COMMAND file
and the NEOS output displayed on the screen is here:
screen output from NEOS
The reputation of the University and the integrity of your degree rests
on the assumption that all work submitted is your own.
We encourage students to discuss the course material and
disseminate what they learn.
In this spirit, DISCUSSION related to the assignments
is acceptable and encouraged.
Please acknowledge all collaboration, discussions, and
sources in your submission,
EXCEPT for the course notes, lecture material, and
discussions with the course staff.
You are expected to write up the solutions on your own.
Copying or paraphrasing a solution from a
fellow student or old solutions qualifies as cheating.
In order to maintain a culture of academic integrity,
members of the University of Waterloo community are expected to
promote honesty, trust, fairness, respect and responsibility.
Read
page on academic integrity.
A student who believes that a decision affecting some aspect of his/her
university life has been unfair or unreasonable may have grounds
for initiating a grievance.
Read
Policy #70 Student Petitions and Grievances.
When in doubt please be certain to contact the department's
administrative assistant who will provide further assistance.
A student is expected to know what constitutes academic integrity
(read
page on academic integrity)
to avoid committing an academic offence, and to take responsibility
for his/her actions. A student who is unsure whether an action
constitutes an offence, or who needs help in learning how to avoid
offences (e.g., plagiarism, cheating) or about "rules" for group
work/collaboration should seek guidance from the course instructor,
academic advisor, or the undergraduate Associate Dean.
For information on categories of offences and types of penalties,
students should refer to
Policy #71, Student Academic Discipline.
For typical penalties, read
Guidelines for the Assessment of Penalties.
A decision made or penalty imposed under Policy 70
(Student Petitions and Grievances) or Policy 71 (Student Discipline)
may be appealed if there is a ground. A student who believes he/she has
a ground for an appeal should refer to
Policy 72, Student Appeals.
A grade of INC will be awarded only to students who cannot write the
final exam for "valid reasons" and who are in "good standing" prior to
the final exam. To be in "good standing" a student must have submitted
and passed ALL assignments, written and passed the midterm exam, and
have attended most of the lectures.
Students seeking an INC grade should discuss with the section
instructor. Documentation is required.
The Office for Persons with Disabilities (OPD), located in Needles
Hall, Room 1132, collaborates with all academic departments to arrange
appropriate accommodations for students with disabilities without
compromising the academic integrity of the curriculum. If you require
academic accommodations to lessen the impact of your disability,
please register with the OPD at the beginning of each academic term.
Before using exams from the past, please read
"What is an Exam?"
The university's
Counselling Services
has posted
Exam Preparation Tips.
The following website has exams from the past:
The MathSoc Online Exambank
Optional reading:
Chapters 19 and 20 of the book
`Linear Programming' by
V.Chvatal.
But be aware that Chvatal's notation differs
from that of CO351.
INFORMS OR/MS Resource Collection.
This is a page for pointers to ALL aspects of operations research and
the management sciences.
Lex Schrijver's web page has some notes on advanced material.
Michel Goeman's web page has some notes on advanced material.
R.K.Ahuja, T.L.Magnanti, and J.B.Orlin.
Network Flows: Theory, Algorithms and Applications.
Prentice-Hall, Englewood Cliffs, N.J., 1993.
Call no. T57.85 A37 1993
V.Chvatal,
Linear Programming,
W.H.Freeman and Company, New York, 1983.
Call No.T57.74.C54 1983
EMAIL: course_number AT student DOT math DOT uwaterloo DOT ca