Network Optimization and Modelling

Synopsis

MTH367 Network Optimization and Modelling will complement MTH355 Basic Mathematical Optimization by studying optimization problems which can be formulated using graphs and networks. These optimization problems may be solved using linear or integer programming techniques but due to its graphical structure, it is easier to use network algorithmic approaches. Additionally, the course will teach students how such algorithms are implemented using the software Gurobi.

Level: 3
Credit Units: 5
Presentation Pattern: Every July

Topics

The Transportation Problem
The Assignment Problem
Terminology of Networks
The Shortest-Path Problem
The Minimum Spanning Tree Problem
The Maximum Flow Problem
The Minimum Cost Flow Problem
The Network Simplex Method
Network Models
Characteristics of Dynamic Programming Problems
Deterministic Dynamic Programming
Probabilistic Dynamic Programming

Learning Outcome

Formulate a given word problem mathematically as a network optimization problem.
Apply the optimality test to justify a solution is optimal.
Draw the network representation of a given network optimization word problem.
Employ the shortest-path algorithm, minimum spanning tree algorithm or maximum flow algorithm to network optimisation problems.
Use dynamic programming to find the optimal solution(s) of a given optimization problem.
Solve network optimisation problems by the network simplex method.

Part-time Programmes / CET Courses

Singapore University of Social Sciences

Network Optimization and Modelling