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
Frugality as a service: the Amazon story
Behind the scenes, Amazon Web Services is one lean machine.
 
Negotiating with the cloud email megavendors
[Blog post] Lessons from Woolworths’ mammoth migration.
 
Qld govt to move up to 149k staff onto Office 365
Australia's largest deployment, outside of the universities.
 
 
Sign up to receive iTnews email bulletins
   FOLLOW US...

Latest VideosSee all videos »

The great data centre opportunity on Australia's doorstep
The great data centre opportunity on Australia's doorstep
Scott Noteboom, CEO of LitBit speaking at The Australian Data Centre Strategy Summit 2014 in the Gold Coast, Queensland, Australia. http://bit.ly/1qpxVfV Scott Noteboom is a data centre engineer who led builds for Apple and Yahoo in the earliest days of the cloud, and who now eyes Asia as the next big opportunity. Read more: http://www.itnews.com.au/News/372482,how-do-we-serve-three-billion-new-internet-users.aspx#ixzz2yNLmMG5C
Interview: Karl Maftoum, CIO, ACMA
Interview: Karl Maftoum, CIO, ACMA
To COTS or not to COTS? iTnews asks Karl Maftoum, CIO of the ACMA, at the CIO Strategy Summit.
Susan Sly: What is the Role of the CIO?
Susan Sly: What is the Role of the CIO?
AEMO chief information officer Susan Sly calls for more collaboration among Australia's technology leaders at the CIO Strategy Summit.
Meet the 2014 Finance CIO of the Year
Meet the 2014 Finance CIO of the Year
Credit Union Australia's David Gee awarded Finance CIO of the Year at the iTnews Benchmark Awards.
Meet the 2014 Retail CIO of the Year
Meet the 2014 Retail CIO of the Year
Damon Rees named Retail CIO of the Year at the iTnews Benchmark Awards for his work at Woolworths.
Robyn Elliott named the 2014 Utilities CIO of the Year
Robyn Elliott named the 2014 Utilities CIO of the Year
Acting Foxtel CIO David Marks accepts an iTnews Benchmark Award on behalf of Robyn Elliott.
Meet the 2014 Industrial CIO of the Year
Meet the 2014 Industrial CIO of the Year
Sanjay Mehta named Industrial CIO of the Year at the iTnews Benchmark Awards for his work at ConocoPhillips.
Meet the 2014 Healthcare CIO of the Year
Meet the 2014 Healthcare CIO of the Year
Greg Wells named Healthcare CIO of the Year at the iTnews Benchmark Awards for his work at NSW Health.
Meet the 2014 Education CIO of the Year
Meet the 2014 Education CIO of the Year
William Confalonieri named Healthcare CIO of the Year at the iTnews Benchmark Awards for his work at Deakin University.
Meet the 2014 Government CIO of the Year
Meet the 2014 Government CIO of the Year
David Johnson named Government CIO of the Year at the iTnews Benchmark Awards for his work at the Queensland Police Service.
Q and A: Coalition Broadband Policy
Q and A: Coalition Broadband Policy
Malcolm Turnbull and Tony Abbott discuss the Coalition's broadband policy with the press.
AFP scalps hacker 'leader' inside Australia's IT ranks.
AFP scalps hacker 'leader' inside Australia's IT ranks.
The Australian Federal Police have arrested a Sydney-based IT security professional for hacking a government website.
NBN Petition Delivered To Turnbull's Office
NBN Petition Delivered To Turnbull's Office
UTS CIO: IT teams of the future
UTS CIO: IT teams of the future
UTS CIO Chrissy Burns talks data.
New UTS Building: the IT within
New UTS Building: the IT within
The IT behind tomorrow's universities.
iTnews' NBN Panel
iTnews' NBN Panel
Is your enterprise NBN-ready?
Introducing iTnews Labs
Introducing iTnews Labs
See a timelapse of the iTnews labs being unboxed, set up and switched on! iTnews will produce independent testing of the latest enterprise software to hit the market after installing a purpose-built test lab in Sydney. Watch the installation of two DL380p servers, two HP StoreVirtual 4330 storage arrays and two HP ProCurve 2920 switches.
The True Cost of BYOD
The True Cost of BYOD
iTnews' Brett Winterford gives attendees of the first 'Touch Tomorrow' event in Brisbane a brief look at his research into enterprise mobility. What are the use cases and how can they be quantified? What price should you expect to pay for securing mobile access to corporate applications? What's coming around the corner?
Ghost clouds
Ghost clouds
ACMA chair Chris Chapman says there is uncertainty over whether certain classes of cloud service providers are caught by regulations.
Was the Snowden leak inevitable?
Was the Snowden leak inevitable?
Privacy experts David Vaile (UNSW Cyberspace Law and Policy Centre) and Craig Scroggie (CEO, NextDC) claim they were not surprised by the Snowden leaks about the NSA's PRISM program.
Latest Comments
Polls
Which bank is most likely to suffer an RBS-style meltdown?





   |   View results
ANZ
  20%
 
Bankwest
  9%
 
CommBank
  11%
 
National Australia Bank
  17%
 
Suncorp
  24%
 
Westpac
  19%
TOTAL VOTES: 1440

Vote