11220 整數規劃與網路分析

Brief course description

Integer programming (IP) aims to solve optimization problems with integer variables. Many practical problems can be formulated and solved using integer programming techniques (i.e. train scheduling, crew scheduling, production planning, and telecommunications). In this course, we will cover the classical and important topics in IP, including formulation, totally unimodular, branch and bound, decomposition and cutting plane algorithms. Network flows is a classical research field with a wide-range of applicability, such as chemistry, physics, computer networking, manufacturing, engineering and transportation. In this course, we will study how to formulate optimization problems as network flow problems and analyze the algorithms designed to solve these problems efficiently. We intend to cover the following network related topics: shortest path, maximum flows, minimum cost flows, minimum spanning trees and multicommodity flows.

Course keywords

Integer Programming, Network Analysis, Operations Research, Mathematical Programming, Optimization

TEXTBOOK

1. 1. Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1993). Network Flows: Theory,
   2. Algorithms and Applications. Prentice Hall, New Jersey.
   3. Wolsey, L.A. (1998). Integer Programming. John Wiley & Son.
   4. Nemhauser, G. L. and Wolsey, L. A. (1988) Integer and Combinatorial
   5. Optimization. John Wiley & Son.
   6. Hillier, F.S. and Lieberman, G.J. (2009) Introduction to Operations Research.
   7. McGraw Hill. 10th edition.

TENTATIVE TOPICS AND SCHEDULE

1. 1. Integer Programming Formulation
   2. Totally Unimodular
   3. Paths, Trees and Cycles
   4. Search Algorithms
   5. Shortest Path Problem-Label Setting Algorithm: Dijkstra’s Algorithm
   6. Shortest Path Problem-Label Correcting Algorithm: Dequeue Implementation
   7. Maximum Flows
   8. Midterm Exam I
   9. Minimum Cost Flows
   10. Minimum Spanning Trees
   11. Lagrangian Relaxation and Network Optimization
   12. Multicommodity Flows
   13. Midterm Exam II
   14. Branch and Bound Algorithm
   15. Cutting Plane Algorithm
   16. Final Exam