9個章節 / 27個單元 / 16小時50分鐘45秒
第 1 章:Course Info
單元 1
54:24
第 2 章:Introduction
第 3 章:Properties of Integer Program
第 4 章:Search Algorithms and Shortest Path Problem
第 5 章:Maximum Flows
第 6 章:Minimum Cost Flows (MCF)
第 7 章:Minimum Spanning Trees
第 8 章:Lagrangian Relaxation
第 9 章:Branch and Bound
課程介紹
課程總時長| 16小時50分鐘45秒
單元數| 9個章節 27個單元

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. 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. 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
課程章節
第 1 章:Course Info
單元 1 - Overview
54:24
第 2 章:Introduction
單元 1 - IP, ..., TSP
45:53
單元 2 - TSP, ..., Discrete Alternatives or Disjunctions
46:29
單元 3 - Definition of Convex Hull & Better Formulation
35:09
單元 4 - Definition of Linear Programming Relaxation & Properties of Integer Program (Cramer’s Rule,Totally Unimodular)
40:08
第 3 章:Properties of Integer Program
單元 1 - Totally Unimodular(TU)
34:33
單元 2 - TU, Network Presentation
37:05
單元 3 - Topological ordering
45:54
第 4 章:Search Algorithms and Shortest Path Problem
單元 1 - Search Algorithm of BFS
36:33
單元 2 - Search Algorithm of DFS, Shortest Path (SP) Problem
42:53
單元 3 - SP Algorithm for Knapsack Problem
34:41
單元 4 - Algorithms for the SP problem: Reaching algorithm
51:24
單元 5 - Algorithms for the SP problem: Dijastra algorithm
47:04
單元 6 - Theorem: Shortest Path Optimality Conditions, Label Correcting Algorithms
47:16
單元 7 - Label Correcting Algorithms: Dequeue Implementation
10:21
第 5 章:Maximum Flows
單元 1 - Introduction, Path-Based Solution Algorithms, Residual Network
26:52
單元 2 - Theorem: Max-Flow Min-Cut; Concept of Preflow Push Algorithm
39:10
單元 3 - Preflow Push Algorithm
35:27
第 6 章:Minimum Cost Flows (MCF)
單元 1 - Assumption, Mathematical Formulation, Risidual Network, Three optimality conditions
31:20
單元 2 - Three optimality conditions (continued)
43:14
單元 3 - Cycle Canceling Aglorithm, Successive Shortest Path Algorithm
41:01
單元 4 - Successive Shortest Path Algorithm (example), Network Simplex Aglorithm
33:35
第 7 章:Minimum Spanning Trees
單元 1 - Introduction, Path/Cut optimality condition
31:20
第 8 章:Lagrangian Relaxation
單元 1 - Introduction of Lagrangian Relaxation (LR), LR with equality constant, LR bounding principle (for minimization problem)
37:26
單元 2 - LR bounding principle, LR with inequality constant, Subgradient Optimization technique with Equality constraint
32:44
單元 3 - Subgradient Optimization Technique with Inequality Constraint, example practice
19:56
第 9 章:Branch and Bound
單元 1 - Branch and Bound, Implicit Enumeration
28:53
作業上傳
查看更多
檔案下載
本課程無檔案
林東盈 教授

> 工業工程與工程管理學系

> 研究領域

生產排程、人員排班、交通運輸、物流管理

✉️ E-mail

👩‍🏫 Introduction

🌐 Personal Website