Discrete and Network Optimisation (ELEN90087)

Overview

Fees	Look up fees

AIMS

The subject focuses on mathematical concepts and algorithms required for solving and analysing a range of different combinatorial and network optimisation problems.

The subject is intended to prepare students to study fundamental topics in combinatorial optimisation and computational geometry, with an emphasis on finding exact solutions. The course will equip students with tools for modelling discrete and network optimisation problems, solving the optimisation models and analysing the results.

INDICATIVE CONTENT

Topics to be covered include: introduction to spanning trees and matroids; the principles of linear programming; network flow problems and the augmented path algorithm; The Euclidean Steiner tree problem and the GeoSteiner algorithm; integer linear programming; NP-complete problems and Cook’s Theorem.

Intended learning outcomes

Intended Learning Outcomes (ILOs):

On completion of this subject, it is expected that the student should be able to:

Describe and solve technical problems involving the basic theory underlying the modelling and solving of discrete and network optimisation problems
Describe the technical challenges in this area and demonstrate the ability to apply the theory to solve a range of relevant problems.

Generic skills

Ability to apply knowledge of basic science and engineering fundamentals;
Ability to undertake problem identification, formulation and solution;
Ability to utilise a systems approach to design and operational performance;
Expectation of the need to undertake lifelong learning, capacity to do so;
Capacity for independent critical thought, rational inquiry and self-directed learning;
Capacity to confront unfamiliar problems;
Ability to evaluate and synthesise academic research and professional literature;
Ability to develop models of practical applications and evaluate their performance by rigorous analytical means.

Last updated: 4 March 2025