The ATOMIC Constraint Programming Platform project will develop G12, a software platform for solving large-scale industrial combinatorial optimisation problems.
The information processing revolution has enabled organisations of all sizes to capture and access accurate and up-to-date information about all their activities and resources. The ATOMIC project will enable this information to be turned to immediate benefit by supporting optimised decision-making and resource allocation.
Advanced software engineering will encapsulate algorithms from several different disciplines, so they can be reused and combined freely. Program development will be accelerated by mapping low-level computation back to the problem model, enabling the programmer to analyse and improve algorithm behaviour.
What will this research achieve?
The project will build G12, a powerful, easy-to-use, constraint programming platform for solving large-scale industrial combinatorial problems. The project plan includes deployment of the platform on four different industrial applications.
The research project is split into four related threads: building richer modelling languages, building richer solving capabilities (search and solver technology), a richer control language mapping the problem model to the underlying solving capabilities and a richer problem-solving environment.
The system will use constraint programming (CP) techniques, which will allow problems to be stated simply and solved efficiently. Solution development time and computing time will be dramatically reduced.
Who will benefit?
This research will enable Australian industry to exploit resources more efficiently. It will support more efficient management of complex private and public utilities such as transportation, communication, power and water. It will help these organisations optimise and justify their strategic decision making and investment.
Latest Research Results
Maximal Density Still Life
The ATOMIC project team has found an optimal solution to the problem of maximal density still life for a 69x69 grid. A still life is a pattern of cells such that according to Conways Game of Life, the cells remain the same in the next generation. The previous best optimal answers known were for 20x20. To show the difference in difficulty the raw search space for 69x69 is 24761 while for 20x20 it is 2400. See still-life for more details.
Resource Constrained Project Scheduling Problems (RCPSP)
RCPSP is a class of problems underlying many important scheduling activities, where we have a finite renewable resource of say manpower, or equipment, or power for completing a set of tasks. PSPLib gives a suite of standard benchmarks for these problems. Using the G12 systems powerful lazy clause generation hybrid solver we are able to solve more of these problems than any other approach in the literature. Our approach closes 60 open problems from the suite. Another advantage of our approach is it does not rely on any clever search specific to the problem, and hence is insensitive to adding side constraints to the problem.
| J30 | J60 | J90 | J120 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 30s | 300s | 1h | 30s | 300s | 1h | 30s | 300s | 1800s | 30s | 300s | 1800s | |
| L&M | 96.0 | 97.7 | 98.1 | 79.4 | 81.2 | 82.1 | 78.3 | 78.5 | 78.8 | 39.2 | 39.8 | 40.0 |
| G12 | 98.75 | 100 | 100 | 85.0 | 88.75 | 89.3 | 79.8 | 81.5 | 82.5 | 42.5 | 44.8 | 45.3 |
Software
G12 additional material
MiniZinc and FlatZinc home page