11220 整數規劃與網路分析

# Core Courses # Graduate Program # Information & Operations Research
9 Lectures / 27 Sections / 16h 50m 45s
Lecture 1：Course Info
Section 1
54:24
Lecture 2：Introduction
Section 1
45:53
Section 2
46:29
Section 3
35:09
Section 4
40:08
Lecture 3：Properties of Integer Program
Section 1
34:33
Section 2
37:05
Section 3
45:54
Lecture 4：Search Algorithms and Shortest Path Problem
Section 1
36:33
Section 2
42:53
Section 3
34:41
Section 4
51:24
Section 5
47:04
Section 6
47:16
Section 7
10:21
Lecture 5：Maximum Flows
Section 1
26:52
Section 2
39:10
Section 3
35:27
Lecture 6：Minimum Cost Flows (MCF)
Section 1
31:20
Section 2
43:14
Section 3
41:01
Section 4
33:35
Lecture 7：Minimum Spanning Trees
Section 1
31:20
Lecture 8：Lagrangian Relaxation
Section 1
37:26
Section 2
32:44
Section 3
19:56
Lecture 9：Branch and Bound
Section 1
28:53
Introduction
Duration｜ 16h 50m 45s
Total Lectures｜ 9 Lectures 27 Sections

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

Dept. Industrial Engineering and Engineering Management

Research Field

Production Scheduling; Crew Scheduling/Rostering; Transportation; Logistics Managemen

✉️ E-mail

👨‍🏫 Introduction

🌐 Personal Website

College of Engineering, National Tsing Hua University © All Rights Reserved