Network Flows, Rafi Hassin

Network Flows - 0365.4125

Lecturer: Prof. Rafi Hassin ( hassin@math.tau.ac.il )
Office: Schreiber Bldg. 107, Phone: 9281
School of Mathematical Sciences
Tel-Aviv University

Intended Audience and Prerequisites

This is a graduate core course in the M.Sc. program in Operations Research. It naturally fits garduate students from other programs such as Computer Science and Industrial Engineering. Undergraduate students who took linear programming are welcome.

Course requirements/Exams

Basic knowledge of linear programming helps but is not required from graduate students who participate in the course. There is a weekly homework set which has some role in the final grade. Solutions to the most interesting/difficult problems will be discussed in class. The grade is mainly determined by a final exam. There is no `official' text book. Some of the material is `classic', some is motivated by the nice solution technique, and some consists of my own research.

Course description

A network is a graph with edge or node weights. These weights describe length, travel time, cost, reliability, or some other number associated with the edge/node. A flow consists of numbers attached to the edges which commonly represent level of `traffic'. A network flow problem asks to compute flow values which satisfy given constraints and minimize the weight associated with the flow. The problem can be formulated as a linear program. The basic network flow problem is the min cost flow problem. It is a fundamental problem in Operations Research and Computer Science and its derivatives are used as building blocks in many algorithms for more general problems. An important feature of the min cost flow problem is that with discrete data (consists of integers) there exists an optimal solution with integral flow values. This property doesn't hold for generalizations of the problem which turn therefore to be computationally much harder. The focus of the course is the min cost flow problem. However, a significant part of it is devoted to special cases such as many variations of the shortest path problem, the minimum cut problem which is the dual of maximum flow and has numerous applications, and more. Attention is also given to other well solved discrete optimization problems: Matching problems and problems on matroids such as the minimum spanning tree problem.