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
Coalition's NBN cost-benefit study finds in favour of MTM
FTTP costs too much, would take too long.
 
Who'd have picked a BlackBerry for the Internet of Things?
[Blog] BlackBerry has a more secure future in the physical world.
 
Will Nutanix be outflanked before reaching IPO?
VMware muscles in on storage startup in hyper-converged infrastructure.
 
 
Sign up to receive iTnews email bulletins
   FOLLOW US...
Latest Comments
Polls
Which is the most prevalent cyber attack method your organisation faces?




   |   View results
Phishing and social engineering
  70%
 
Advanced persistent threats
  3%
 
Unpatched or unsupported software vulnerabilities
  11%
 
Denial of service attacks
  6%
 
Insider threats
  10%
TOTAL VOTES: 647

Vote