Discrete and Network Optimisation (ELEN90087)

Graduate courseworkPoints: 12.5Not available in 2025

You’re viewing the 2025 Handbook:
Or view archived Handbooks

Overview

FeesLook 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

Eligibility and requirements

Prerequisites

Admission into a research higher degree (MPhil or PhD) in Engineering.

Corequisites

None

Non-allowed subjects

None

Recommended background knowledge

Familiarity with some basic optimisation models and problems is recommended, particularly linear programming, integer programming and minimum spanning tree algorithms.

Inherent requirements (core participation requirements)

The University of Melbourne is committed to providing students with reasonable adjustments to assessment and participation under the Disability Standards for Education (2005), and the Assessment and Results Policy (MPF1326). Students are expected to meet the core participation requirements for their course. These can be viewed under Entry and Participation Requirements for the course outlines in the Handbook.

Further details on how to seek academic adjustments can be found on the Student Equity and Disability Support website: http://services.unimelb.edu.au/student-equity/home

Last updated: 4 March 2025

Assessment

DescriptionTimingPercentage

Continuous assessment, consisting of two written homework assignments not exceeding 30 pages in total and a 15 minute oral presentation. The first assignment will be due mid-semester (approximately week 7). The second assignment and oral presentation will be due in approximately week 11 or 12

  • 50-60 hours (of work required)
From Week 7 to Week 1240%

A written examination

  • 3 hours
Hurdle requirement: Students must pass the written exam to pass the subject.		End of semester60%

Additional details

Intended Learning Outcomes (ILOs) 1 and 2 are assessed in the final exam and through the continuous assessment.

Last updated: 4 March 2025

Dates & times

Not available in 2025

Time commitment details

200 hours

Last updated: 4 March 2025

Further information

  • Texts

    Prescribed texts

    There are no specifically prescribed or recommended texts for this subject.

  • Related Handbook entries

    This subject contributes to the following:

    TypeName
    CourseDoctor of Philosophy - Engineering
  • Available through the Community Access Program

    About the Community Access Program (CAP)

    This subject is available through the Community Access Program (also called Single Subject Studies) which allows you to enrol in single subjects offered by the University of Melbourne, without the commitment required to complete a whole degree.

    Please note Single Subject Studies via Community Access Program is not available to student visa holders or applicants

    Entry requirements including prerequisites may apply. Please refer to the CAP applications page for further information.

    Additional information for this subject

    Subject coordinator approval required

  • Available to Study Abroad and/or Study Exchange Students

    This subject is available to students studying at the University from eligible overseas institutions on exchange and study abroad. Students are required to satisfy any listed requirements, such as pre- and co-requisites, for enrolment in the subject.

Last updated: 4 March 2025