Handbook home
Discrete and Network Optimisation (ELEN90087)
Graduate courseworkPoints: 12.5Not available in 2020
For information about the University’s phased return to campus and in-person activity in Winter and Semester 2, please refer to the on-campus subjects page.
Please refer to the LMS for up-to-date subject information, including assessment and participation requirements, for subjects being offered in 2020.
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: 30 January 2024
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: 30 January 2024
Assessment
Due to the impact of COVID-19, assessment may differ from that published in the Handbook. Students are reminded to check the subject assessment requirements published in the subject outline on the LMS
Description | Timing | Percentage |
---|---|---|
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
| From Week 7 to Week 12 | 40% |
A written examination
| End of semester | 60% |
Additional details
Intended Learning Outcomes (ILOs) 1 and 2 are assessed in the final exam and through the continuous assessment.
Last updated: 30 January 2024
Dates & times
Not available in 2020
Time commitment details
200 hours
Last updated: 30 January 2024
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:
Type Name Course Doctor 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.
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: 30 January 2024