CS 719: Network Flows - Spring 1997

Schedule

  Lecture:             8:50 - 9:40 MWF, 1257 CS&S
               Start at 8:30 throughout February
  No classes:          Friday 14 March, Monday 17 March, 
               Wednesday 19 March, Friday 21 March.
  Course E-mail:       cs719-1list@cs.wisc.edu

Instructor: Michael C. Ferris

  Office:       6391 CS&S
  Telephone:    262-4281
  E-mail:       ferris@cs.wisc.edu
  Office Hours: 11:00 - 1:00 Mondays

Teaching Assistant: Lee Yuh-Jye

  Office:       6393 CS&S
  Telephone:    262-6593
  E-mail:       yuh-jye@cs.wisc.edu
  Office Hours: 2:00 - 3:30 Wednesdays and 
                1:00 - 2:00 Thursdays

General Course Information

• By taking advantage of the special structure of linear network optimization problems, a "graphical" version of the simplex method is developed. This "network simplex method" is about 100 times faster than the ordinary simplex method, and has nice integrality properties that allow the solution of some combinatorial problems such as assignment, matching, and min cut problems. Variants of the network simplex method are also presented for convex, non-convex, generalized, and multicommodity networks. Some alternative new methods with good complexity bounds will also be considered. Particular applications in operations research, business and the sciences will be discussed. The solution of large scale problems using state of the art packages will also be demonstrated and used in the course.

  ---

• Prerequisite CS 525 or Knowledge of Linear Programming
• Course Outline
  • Paths, Trees and Cycles (Data Structures)
  • Shortest Paths
  • Max Flow
  • Min Cost
  • Network Simplex Method
  • Generalized Flows (Convex, equilibria)
  • Lagrangian Relaxation
  • Multicommodity Flows
  • Applications
• Homework assignments: 40% of grade
• Project assignment: 20% of grade (due in class, Wednesday May 7)
• Final examination: 40% of grade (Monday May 12, 2:45 - 4:45, CS 1289) Some representative exam questions can be found in Old exam questions.

Recommended Text:

• Network Flows, Ravindra K. Ahuja, Thomas Magnanti and James Orlin, Prentice Hall.

Other Useful Texts:

• Linear Programming, V. Chvatal, Freeman, 1980.
• Linear Network Optimization, D. Bertsekas, MIT Press, 1991.

Assignments

• Homework 1 (due Friday January 31, 1997).
• Homework 2 (due Friday February 7, 1997).
• Homework 3 (due Friday February 14, 1997).
• Homework 4 (due Friday February 21, 1997).
• Homework 5 (due Friday February 28, 1997).
• Homework 6 (due Friday March 7, 1997).
• Homework 7 (due Wednesday April 2, 1997).
• Homework 8 (due Friday April 4, 1997).
• Homework 9 (due Friday April 11, 1997).
• Homework 10 (due Friday April 18, 1997).
• Homework 11 (due Friday April 25, 1997).
• Homework 12 (due Friday May 2, 1997).
• Homework 13 (due Friday May 9, 1997). Homework 12 (due Friday May 3, 1996).

Computing Information

• Unix Orientation Sessions

      Unix Orientation sessions will be held as follows:
  
          Wednesday Jan 22    5pm, 6pm
          Thursday Jan 23     5pm, 6pm
  
          Monday Jan 27       5pm, 6pm
          Tuesday Jan 28      5pm, 6pm
          Wednesday Jan 29    5pm, 6pm
          Thursday Jan 30     5pm, 6pm
  
          Room 2310 CS
  
      The orientation session includes a 20 minute video tape and
      30-45 minute hands-on session in the user rooms. New Unix users
      are strongly encouraged to attend.
  

• Account Initialization

      Registered students who had a CSL Unix account last semester
      have the same account this semester. They should be able to
      login using the same login name and password as last semester.
  
      Registered students who had a vectra lab account (for CS 110 or
      CS 302) have the same login name and password on the Unix
      workstations.   
  
      Registered students who did not have an account last semester
      should initialize their account by logging in to a Unix
      workstation as user "newuser". There are signs in the user 
      rooms explaining how to use newuser, and running newuser is
      including in the Unix Orientation hands-on session.
  
      NOTE: We add accounts for students every afternoon based on
            registration information from the registrar's
            database. Newly created accounts are active as of the next
            morning. 
  
            There may be an additional delay between the time the
            student registers via touch-tone and when the data is
            avaliable to us.  
  

• Introduction to UNIX at UW

•    To set up your login so that you have access to GAMS:
     > cp ~cs719-1/public/.cshrc.local ~/.cshrc.local
     > source ~/.cshrc.local
     This alters your path and sets up the GAMS directory appropriate
     for solaris machines on it.
  

• Course Machines SOL lab, 1370 CS&S

Mathematical Programming at UW

• Home Page
• Courses