Text | | Network Flows: Theory, Algorithms and Applications,by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, published by Prentice Hall, 1993 This book won the Institute for Operations Research and the Management Sciences (INFORMS) Lanchester Prize for the best contribution to OR/MS published in English in 1993.
|
Course Web Page | | http://www.public.iastate.edu/~smryan/ie510/index.htm Homework assignments and solutions and other material will be made available here as the semester progresses. Check it often!
|
Description | | Many optimization problems can be modeled in terms of flows through networks. A network formulation can provide a clear visual representation of the problem and enable efficient solution methods. In particular, many discrete and nonlinear problems can be solved very efficiently as network flows. Homework exercises will be assigned every 1-2 weeks to be handed in and graded. Students will complete semester projects chosen from their own interests or a suggested list. There will be three exams. |
Tentative Topic List | | The following sections in Ahuja, Magnanti and Orlin: 1.1-4 Introduction 2.1-5 Paths, Trees and Cycles 3.1-6 Algorithm Design and Analysis 4.1-5 Shortest Paths: Label-Setting Algorithms 5.1-6 Shortest Paths: Label-Correcting Algorithms Chapters 4 and 5 will be supplemented with instructor’s notes on dynamic programming formulation, application and methods. 6.1-6 Maximum Flows: Basic Ideas 7.1-2,6-7 Maximum Flows: Polynomial Algorithms 9.1-7 Minimum Cost Flows: Basic Algorithms 11.1-5, 12 Minimum Cost Flows: Network Simplex Algorithms 12.1-6 Assignments and Matchings 13.1-5 Minimum Spanning Trees 19.7-9 Additional Applications |
A "Tutorial on Computational Complexity" by Craig Tovey (2002) is in Interfaces Vol 32, No. 3. (If you follow this link from an ISU computer, you should be logged on to Extenza-INFORMS with full access to articles.)
Class notes:
No comments:
Post a Comment