Optimisation
“Our fundamental research goal is to build an environment in which techniques from stochastic programming to business rules, and from interior point methods to propositional satisfiability, not only can be, but actually are, tightly integrated so as to provide a functionality much greater than the sum of their parts.
Our vision, in terms of impact, is to use the scientific results above be able to model any organisation or system, simulate and optimise it.”
Optimisation is the "science of better". Research at NICTA on combinatorial optimisation addresses multi-faceted questions such as how best to schedule trains on a network to meet passenger demand, what is the best course of action to restore service in a faulty power system, whether there is a better folding for a protein, or how best to operate a supply chain. We focus on the interface between constraint programming, operations research, satisfiability, search, automated reasoning, machine learning, simulation and game theory, exploring methods that combine techniques from these different areas. These techniques in turn enable us to attack basic optimisation problems such as graph matching, packing, path-finding, planning and scheduling, resource allocation, routing, and diagnosis, and applications in which several of those basic problems interact.
The need to optimise our planning and use of resources is widely acknowledged. At the worldwide level, these resources include water, food, and energy. In government and industry organisations, they include people and their time, financial capital and budgets, buildings and infrastructure and the many different resources used in day-to-day activities. Optimisation requirements increasingly arise at the individual level, in questions such as how travel to work, where to shop, and which phone contract to select. Moreover these different levels of optimisation impact each other. For example individual choices affect and are affected by the choices made by organisations, and organisational choices are impact and are impacted by worldwide resources.
Yet optimisation arises in many other areas. When diagnosing faults and breakdowns, the optimisation question is what is the simplest cause; medical diagnosis seeks the most likely explanation, while minimising the possible consequences of error; many applications in physics, chemistry and bio-informatics require optimisation techniques to seek the minimum energy configuration of a system; to design the best roads, buildings, engines, dams and networks it is often necessary to solve optimisation problems; and optimisation even arises in the construction of mechanisms within which people and organisations interact, from auctions to supply chains.
Several trends are likely to provide important new opportunities for optimisation in the next decade which will shape the research agenda:
- Environment: pressure to reduce man's footprint on the Earth, to limit CO2 production, and to consume less will create many new challenging optimisation problems.
- Energy: on the other side, rising energy costs, diminishing reserves, and political instability in many oil producing countries, will create immense pressure to optimise the production and consumption of energy.
- Water: the increasing world population and the impact of global warming, will at the same time create immense pressure to optimise the distribution and consumption of scarce water resources.
- Bioinformatics: genomics, proteomics and the many other "omics" herald a data rich future for biology and health, with many new optimisation problems.
Contact
Leader, Optimisation Research Group
Sylvie Thiebaux
Sylvie.Thiebaux<at>nicta.com.au