NICTA develops decision-making software

Algorithm solves Sudoku, inventory, scheduling problems.

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."