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 © iTnews.com.au . All rights reserved.


NICTA develops decision-making software
 
 
 
Top Stories
Beyond ACORN: Cracking the infosec skills nut
[Blog post] Could the Government's cybercrime focus be a catalyst for change?
 
The iTnews Benchmark Awards
Meet the best of the best.
 
Telstra hands over copper, HFC in new $11bn NBN deal
Value of 2011 deal remains intact.
 
 
Sign up to receive iTnews email bulletins
   FOLLOW US...
Latest Comments
Polls
Who do you trust most to protect your private data?







   |   View results
Your bank
  38%
 
Your insurance company
  4%
 
A technology company (Google, Facebook et al)
  8%
 
Your telco, ISP or utility
  8%
 
A retailer (Coles, Woolworths et al)
  3%
 
A Federal Government agency (ATO, Centrelink etc)
  19%
 
An Australian law enforcement agency (AFP, ASIO et al)
  14%
 
A State Government agency (Health dept, etc)
  6%
TOTAL VOTES: 1892

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