IEEM 5132-0

Brief

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. Basic mathematical programming concepts ar

Description

Course keywords: Integer Programming, Network Analysis, Operations Research, Mathematical Programming, Optimization INSTRUCTOR 林東盈 (Dung-Ying Lin); Email: dylin@ie.nthu.edu.tw TEXTBOOK 1. Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall, New Jersey. 2. Wolsey, L.A. (1998). Integer Programming. John Wiley & Son. 3. Nemhauser, G. L. and Wolsey, L. A. (1988) Integer and Combinatorial Optimization. John Wiley & Son. 4. Hillier, F.S. and Lieberman, G.J. (2009) Introduction to Operations Research. McGraw Hill. 10th edition. COURSEWORK REQUIREMENTS Homework assignments and presentation: 20% Midterm examination I*: 25% Midterm examination II*: 25% Final examination*: 30% *No make-up exam TENTATIVE TOPICS AND SCHEDULE 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 Regarding student's use of AI: conditionally open; please specify how generative AI will be used in course output

Timetable

Scores

Average Percentage 82.96

Std. Deviation 7.78

Remarks

本課程為16週課程,大四生需老師同意後方可加簽 Senior students must ask teacher's approval to register

Restrictions

限工工系碩士班博士班專班,工工在職班碩士班博士班專班

Compulsory

Elective

Cross Discipline

First Specialization

Second Specialization