Modelling, optimisation and visualisation
Our aim is to develop optimisation and visualisation technology that can help people make better, more informed decisions. This will enable decision makers in large and small organisations to improve the quality and efficiency of their services. The most difficult and important decision problems are often combinatorial optimisation problems, where we must find a combination of choices that satisfies certain constraints and optimises some objective.
Imagine travellers waiting for a flight that has just been delayed. The airline must find a new schedule by choosing a new departure gate, time and runway slot for that flight, and possibly for the subsequent legs of the passengers' itineraries. The schedule will be optimal if it minimises the inconvenience to travellers and the cost to the airline.
Combinatorial problems such as these pervade all aspects of modern life - social, environmental and economic. Finding high quality solutions to these problems allows us to better use our limited resources, which benefits our industry, our health system, our security and our environment. Solving these problems is also key to accelerated research in areas such as bio-informatics, wiser investment and better engineering.
Combinatorial optimisation problems can now easily be modelled in expressive high-level languages and solved using a wide range of solving techniques. While the particular model used is crucial to the quality of the solutions obtained for a problem, designing a good model is difficult even for experts and requires great time and experience. This prevents organisations from benefiting from recent breakthroughs in optimisation technology. This flagship theme aims at developing technology that (a) extends the expressiveness of modelling languages, and (b) simplifies the task of finding the best model for a given problem. This research builds on our previous work, in collaboration with researchers at Melbourne University, designing Zinc, a modelling language that, together with its subset, MiniZinc, has become a standard modelling formalism at international meetings.
Given a model for a problem, the most crucial step towards finding a high quality solution is the choice of an appropriate solving technique, or combination of techniques. However, this requires overcoming two difficult hurdles: accessing and integrating solving techniques, and understanding how the model's characteristics influence the efficiency of the solving technique. This flagship theme aims to develop technology that (a) makes it easier to use and combine different solving techniques, (b) helps users select and apply the right solving techniques for their models, and (c) provides useful information to explain the causes of and remedies for poor solving performance. This research builds on our previous work on automatic model analysis and on the design and implementation of Gecode, the fastest publicly available constraint solver.
Appropriately visualising information is crucial for good decision making. Effective visualisation allows the decision maker to better understand the problem and trust the solution, interactively explore possible solutions and to clearly communicate the benefits and tradeoffs behind their decisions to all stake-holders. This flagship theme focuses on both visualisation techniques for information visualisation and accessibility as well as the use of constrained optimisation techniques in visualisation and document layout.
- Mark Wallace
|KTH Royal Institute of Technology, Sweden|
|KU Leuven, Belgium|
|Monash Academy for Cross and Interdisciplinary Mathematical Applications (MAXIMA)|
|National ICT Australia (NICTA)|
Graphics Viewer using Vibration, Interactive Touch, Audio and Speech. GraVVITAS is a multi-modal presentation device which uses touch screen and haptic feedback technologies to provide access to graphics for blind people. A data glove equipped with vibrating motors provides haptic feedback when the finger is over a graphic element on the tablet computer. GraVVITAS also provides speech and 3D non-speech audio feedback to help the user with navigation. A $5,000 Honorable Mention in the 2012 Touch of Genius awards, National Braille Press of USA, was awarded to the team of Cagatay Concu, Kim Marriott, and John Hurst for this project.
Many combinatorial problems have symmetries, so that different choices in the problem lead to "symmetrically equivalent" situations. Exploiting such symmetries (called "symmetry breaking") is important because it can yield order-of-magnitude speed-ups when solving the problem, thanks to the fact that once a choice is explored, all symmetric choices can be ignored. Unfortunately, current methods can also yield considerable slowdowns, and until now no available solving system embedded a symmetry breaking method. The aim of this project was to develop an automatic symmetry breaking method that never yields a major slowdown but often gives major performance improvements. This aim has been achieved and the resulting method has been integrated in the popular ECLiPSe and Gecode constraint programming systems.
Analysis of Peak-Hour Congestion in Melbourne
We have worked with the Melbourne road authority, VicRoads, to investigate how peak-hour congestion builds up in Melbourne, and ways of improving traffic flow by changing traffic signal cycles. The research starts from an analysis of traffic density and traffic flow: as traffic density increases up to a certain level, the flow of vehicles also increases, but beyond that level increased density leads to reduced flow. This is the level where traffic congestion starts. We have taken data for a whole year from VicRoads and can show average traffic density across Mondays during school term, or any other selection of days or times. Those points where density is high enough to reduce flow, we show in red - for congestion. We have analysed traffic build-up before rush-hour using data mining techniques so as to detect patterns which precede the onset of congestion. When these patterns arise, the aim is to change traffic signal cycles so as to postpone traffic congestion, and shorten journey times.
The following are potential topics for PhD or Masters projects in the area of Modelling, Optimisation and Visualisation. Scholarships for local and international students are available on these priority themes. If you are interested, please contact one of the supervisors.
|Profiling Statistics for Constraint Programs|
|Visualising Execution Profiles of Constraint Programs|
|Optimal network diagram layout using constraint optimisation|
|Software engineering tools for modelling constraint problems|
|Visualisation of Dynamically Changing Command Structures in Emergency Services|
|Visual exploration of graph databases|