Welcome to Math 514,
Autumn 2008
(last updated 11/6/2008)
- HW 4 is posted below.
- Erratum for Rockafellar's book is posted below.
- The course project (due Dec 10) is posted here
.
For option 2 in the course project, you can assume the problem data
are integer-valued. Some test problems are:
Problem 1: |N|=4, |A|=5, optimal cost = 14
Problem 2: |N|=20, |A|=80, optimal cost = 30464
Problem 3: |N|=49, |A|=520, optimal cost = 1.76775707E+09
(caution: this network has some parallel arcs)
Problem 4: |N|=10000, |A|=60000, optimal cost = 21514702 (maybe)
Problem format:
Row 1 indicates |N| and |A|.
Rows 2 to |A|+1 correspond to arcs, indicating the start node, end node, cost, upper capacity of each arc. (lower capacity is assumed to be zero.)
The last |N| rows correspond to nodes, indicating the supply at each node.
Course Info:
- Instructor:
Paul Tseng
- E-mail:tseng@math.washington.edu
- Office:
Padelford C-344
- Office Hours:
Thursdays 2:00-3:30 or whenever I am free
- Lecture:
M, W, F 10:30-11:20 AM, Room
BLD 392
- Textbook:
R. T. Rockafellar, Network Flows and Monotropic Optimization ,
Athena Scientific
- Course Syllabus (pdf)
Prerequisites:
A desire to understand and precise logical reasoning
About this course:
This course will give an overview of
classical and modern topics in network optimization and, in particular,
shortest path,
max flow min cut, optimal assignment, linear cost flow, traveling salseman problem,
Lagrangian relaxation.
This will involve problem models, theory, and algorithms.
A bit of programming might also be involved.
Handouts/Slides (Pdf files)
Homeworks (Pdf files)
Links of Interest: