NICTA develops decision-making software


Algorithm solves Sudoku, inventory, scheduling problems.

NSW Audit Office - Awareness - Isue 2010/07 - August 2010

Australian research institute NICTA has entered into discussions to commercialise software for identifying the best possible set of decisions under multiple constraints.

The so-called 'G12' constraint programming platform used a 'lazy clause generator' to speed large-scale, industrial decision-making processes by orders of magnitude.

Developed by University of Melbourne professor Peter Stuckey, the lazy clause generator combined two approaches: high-level constraint programming and low-level Boolean satisfiability.

"It's a hybrid of two technologies," Stuckey explained. "You write a high-level description of the problem that you're trying to solve.

"As you search to find a solution, the lazy clause generator is generating a low-level description of the problem to record sets of decisions that were wrong, so you never have do them again."

The G12 platform could be used by transport companies and Government agencies for combinatorial problems like airline crew scheduling, resource allocation and hospital staff rostering.

Stuckey described rostering as a complicated process that involved rules like allocating sufficient nurses to each ward, and not having any nurse do too many night shifts in a row.

Another example of a combinatorial problem was Sudoku, a number puzzle that required digits to be entered in 9x9 grid so that each column, row and 3x3 sub-grid contained all digits from one to nine.

"If people solve Sudoku, they'd sort of know how this sort of technology works," Stuckey said. "You can't just arbitrarily fill in the boxes; each decision you make affects other decisions."

"The idea is trying to reason, as best as you can, what decisions are impossible. Computers are very good at guessing and do lots of search."

Stuckey said there were other techniques - including local search methods, evolutionary algorithms and mixed integer programming - that excelled at solving different types of combinatorial problems.

Lazy clause generation performed particularly well in benchmark problems where the optimal solution was difficult to identify, he said.

NICTA was in discussions with commercial partners to build a proof-of-concept G12 prototype, which would focus initially on solving scheduling problems within the partner organisation.

"If that's successful, then we would develop that into a product," Stuckey said, declining to disclose details of the partner and project timeline.

For the lazy clause generator, Stuckey was last week awarded the $10,000 inaugural Google Australia Eureka Prize for Innovation in Computer Science.

While the software could support more efficient management, Stuckey expected human managers to retain the final say on any resultant decisions.

"As we realise that we can't make decisions as well as these sophisticated optimisation algorithms, then more and more would be delegated to computing," he said. "[But] people don't want to give up the idea of making decisions.

"In reality, what happens with combinatorial optimisation software of any form is that you run it, you get a solution and then a manager or someone would interact with it and say [what] they want to be changed, because in the end, people want to feel like they're in control of the process."

Copyright © . All rights reserved.

NICTA develops decision-making software
Top Stories
Toll Group to go Google
Poaches Woolworths project manager.
How News Corp's CIO tackled skills in his race to the cloud
What to do when your team’s talents are no longer needed.
Photos: How Thodey transformed Telstra
From turbulent Trujillo to Australia's leading telco.
Sign up to receive iTnews email bulletins
Latest Comments
Who do you trust most to protect your private data?

   |   View results
Your bank
Your insurance company
A technology company (Google, Facebook et al)
Your telco, ISP or utility
A retailer (Coles, Woolworths et al)
A Federal Government agency (ATO, Centrelink etc)
An Australian law enforcement agency (AFP, ASIO et al)
A State Government agency (Health dept, etc)

Do you support the abolition of the Office of the Information Commissioner?

   |   View results
I support shutting down the OAIC.
I DON'T support shutting the OAIC.