-
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 255/355 or CM 340.
Not open to General Mathematics students.
-
Time & Place:
-
12:30-1:20 MWF MC4064
-
Office hours:
-
Instructor
J.Cheriyan MC 5034 phone x35591 Wed 2:00-3:00
(jcheriyan@uwaterloo.ca)
Teaching Assistant:
Z.Gao TBA phone TBA TBA
(z9gao@uwaterloo.ca)
Network Flow Theory - C&O 351.
This book is available from the UW Media.doc location in MC 2018.
Please look up the course webpage on D2L/LEARN regularly for updated info.
Final 55%
Midterms 1 and 2 30%
Assignments 15%
To pass the course, a pass in the final exam is required.
The first midterm exam is on June 5, Wednesday, and
there are two sessions (you may write in either session, but
those writing in the early session have to stay in the exam room
till 7pm).
-
June 5 (W) Session.1: 5:00-6:50 in MC 4063
-
June 5 (W) Session.2: 7:00-8:50 in MC 4063
The second midterm exam is on July 3, Wednesday, and
there are two sessions (you may write in either session, but
those writing in the early session have to stay in the exam room
till 7pm).
-
July 3 (W) Session.1: 5:00-6:50 in MC 4063
-
July 3 (W) Session.2: 7:00-8:50 in MC 4063
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 your submission
(there is no need to acknowledge help from
the course staff or from the course material).
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 |
May.10 |
May.17 |
CO350 Review, 1 |
| #2 |
May.17 |
May.24 |
1, TPs |
| #3 |
May.24 |
May.31 |
TPs, 2 |
| #4 |
June.7 |
June.14 |
TPs, 2, 3 |
| #5 |
June.14 |
June.21 |
2, 3 |
| #6 |
June.21 |
June.28 |
3 |
| #7 |
July.5 |
July.12 |
3, 4 |
| #8 |
July.12 |
July.19 |
4 |
| #9 |
July.19 |
July.26 |
TBA |
A missed midterm exam or a missed 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.
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. Send an email to instructor/TA to
fix an appointment.
Info on AMPL and its use from the CO370 web page.
Tutorial on AMPL (PDF file, 13 pages)
Frequently Asked Questions about AMPL
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.
The university's
Student Success Office (SSO)
has posted
resources and tips for exams.
Before using exams from the past, please read
"What is an Exam?" (login required)
The following website has exams from the past:
The MathSoc Online Exambank (login required)
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