The Constraint Programming Platform project is developing 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 Constraint Programming Platform 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 is building G12, a powerful, easy-to-use, constraint programming platform for solving large-scale industrial combinatorial problems.
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 uses constraint programming (CP) techniques, which will allow problems to be stated simply and solved efficiently. Solution development time and computing time can 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.
The Intelligent Fleet Logistics project commenced in June 2008 and is combining operations research algorithms for vehicle routing with the flexibility of constraint programming. This research is use inspired, being driven by real-world applications of the technology to deliver systems applicable to industry requirements.
Best Paper 2009
O. Ohrimenko, P.J. Stuckey, and M. Codish. Propagation via lazy clause generation. Constraints, 14(3):357–391, 2009. [ERA A]. [PDF]
Latest Research Results
Dynamic Programming for Free
The CPP team have developed a method for automatically caching subproblems visited during search, so that when an identical subproblem is met this search can be avoided. This can increase solving time by orders of magnitude when identical subproblems arise during search. It can be seen as a way of gaining the advantages of dynamic programming without specifically modelling an optimization problem as a recurrence relation. The system is fully automatic and works on arbitrary Minizinc models. See autocache for more details.
CP 2009 impact
The International Conference on Principles and Practice of Constraint Programming is the peak conference on constraint programming. For 2009, 10 out of 61 accepted papers have authors from the Constraint Programming Platform project.
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. See RCPSP for more details.
| J30 | J60 | J90 | J120 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 15s | 300s | 1800s | 15s | 300s | 1800s | 15s | 300s | 1800s | 15s | 300s | 1800s | |
| L | - | 100 | 100 | - | 84.2 | 85.0 | - | 78.5 | 79.4 | - | 41.3 | 41.7 |
| G12 | 98.75 | 100 | 100 | 85.8 | 89.0 | 89.6 | 80.0 | 81.9 | 82.7 | 42.7 | 45.8 | 47.0 |
Comparison of percentage of problems solved to optimality in different times versus [L] Laborie, P.: Complete MCS-based search: Application to resource constrained project scheduling. In: L.P. Kaelbling, A. Saffiotti (eds.) Proceedings IJCAI 2005, pp. 181–186.
Software
G12 additional material
MiniZinc and FlatZinc home page
MiniZinc Wiki
Earlier Research Results
Major achievements of the Constraint Programming Platform project to date are:
- The design of a solver independent modelling language Zinc. This allows the problem modeller to express their problem in a high level manner, close to the actual problem domain, without determining how the problem will be solved.
- selected publication: The design of the Zinc modelling language. Constraints 13(3):229-267. 2008 [PDF].
- The design of a solver mapping language Cadmium. Cadmium is a term rewriting language that allows the concise specification of transformations from Zinc to Zinc. Transformations are used to map the original Zinc model to a model that can be handled by one of the underlying solving technologies, or a hybrid of the underlying solving technologies.
- selected publication: Cadmium: An implementation of ACD term rewriting. Proceedings of ICLP2008, LNCS 5366, pages 531-545, 2008. [PDF]
- A design pattern for column generation hybrid solving. Column generation is effectively unbeatable solving strategy for many problems. We can annotate a Zinc model to specify the master and subproblems that arise in the model, and this is then automatically translated to an executable that performs the column generation, including handling search (branch and price) and automatically aggregating identical subproblems, and disaggregating them as search progresses. This enable the construction of branch and price solutions in hours as opposed to weeks of expert programming time.
- selected publication: From high level model to branch and price solution in G12. Proceedings CPAIOR08. LNCS 5015, pages 218-232, 2008. [PDF]
- A hybrid solving approach, lazy clause generation, that maintains the best features of CP solving (programmable search, and high-level models) with that of SAT solving (nogood recording for search reduction, and conflict driven search). The resulting solver is state of the art for scheduling problems such as RCPSP (see above)
- selected publication: Propagation via lazy clause generation. Constraints 14(3):357-391. 2009. [PDF]
- The frontrunner for a standard modelling language for CP, MiniZinc. MiniZinc is designed as an quite expressive modelling language, which translates to FlatZinc, a problem instance language designed to be close to CP solvers. Building a front end to a solver to support MiniZinc is thus a fairly straightforward task. MiniZinc is currently supported by most of the major CP solvers: Eclipse, Gecode, SICStus as well as G12.
- selected publication: MiniZinc: Towards a standard CP modelling language. Proceedings CP2007. LNCS 4741. pages 529-543, 2007. [PDF]
- Maximum Density Still Life: The Constraint Programming Platform 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.