The optimisation platform project team builds an optimisation platform that will dramatically simplify the solving of this new generation of complex optimisation applications by supporting rapid prototyping, deep solver hybridisation, data-intensive optimisation, and decision-making under uncertainty.
Optimisation Platforms
As the need for optimisation technology increases, it is essential to lower the barrier of entry to using this technology. Many optimisation problems are simple to solve using modern technology, but the problem owners are unaware or unable to use the optimisation technology already available. While problem modelling is a skill that needs to be learnt, we need to make it far easier to learn and apply this skill. To this end we need universal modelling languages that can be used to “model and run”, that is, once a problem is modelled correctly, the underlying optimisation system automatically determines what is the most appropriate technology, without any further intervention from the modeller.
As optimisation tackles increasingly more complex and large-scale applications, the demands placed on the underlying technology in terms of speed, scale, and expressive power generate fundamental computational challenges. The complexity of this new generation of applications places a significant cognitive burden even on expert practitioners. For these applications hybridisations of major technologies, such as constraint programming, mathematical programming and local search, are becoming the de-facto standard for addressing them. At the same time, the scope of optimisation has broadened from a focus on routing and scheduling to other areas such as integrated resource planning; operational decision-making under uncertainty, with data being delivered continuously in real-time to the optimisation engine; and data-intensive optimisation where optimisation technology is applied to very large data sets. This places new requirements on the technology which now needs to find high-quality solutions under time constraints, exploit uncertainty, deal with large data sets, and be integrated in complex runtime environments.
Mission
The platform project aims to build the next generation of optimisation technology. The technology will be: easy to use, easy to integrate in applications, and capable of tackling challenging future optimisation problems efficiently. The next generation optimisation technology will be agnostic of the optimisation method used allowing the same problem model to be solved using for example, mixed integer programming, dynamic programming, constraint programming or local search. The team aims to unify the different optimisation research communities by allowing easy comparison of different methods on the same problem, and breaking down the current silos or knowledge.
History
Members of the platform team have been responsible for driving new directions in optimisation for the last 25 years. They developed two of the first three modern constraint programming systems: CHIP and CLP(R), laid the theoretical foundations for constraint programming, and developed many important constraint programming systems including Numerica, Localizer, Eclipse Prolog, OPL, HAL, Comet and Gecode. The G12 project which was the direct ancestor of the platform project developed the Zinc and MiniZinc solver independent modelling languages, as well as the award winning Lazy Clause Generation hybrid approach to constrained optimisation, which defines the state-of-the-art for many well studied scheduling problems. The G12 project lead to the spin out company Opturion which develops optimisation solutions for leading companies using Zinc.
Research Focus
Modelling
The first challenge users face when trying to solve optimisation problems is to express the problem in a format that is suitable for the chosen optimisation technology. This process, called modelling, is indeed one of the major obstacles preventing widespread adoption of optimisation technology. Our aim is to make modelling easy and optimisation technology accessible for every software engineer by expressing problems at a high level of abstraction, making combinatorial substructures explicit, and supporting advanced modelling techniques such as optional decisions and stochastic information.
Model Analysis and Transformation
The performance of most optimisation algorithms depends crucially on the quality of the input models. Writing “good” models is hard: it requires both a deep understanding of the problem and of the solving technology. An important focus of our research is therefore on techniques for analysing models, providing interactive feedback to the users, and improving the automatic translation to lower-level, solver-specific formulations.
Modelling technologies
The core technology used to solve an optimisation problem is of crucial importance in term of efficiency. Several major technologies differ greatly in their capabilities to solve different classes of problems. Our aim is to provide more efficient and scalable solving technologies for a wide range of problems. We will design and develop a flexible and scalable optimisation platform that integrates and hybridises the major technologies as well as novel techniques that we are developing.
Enabling Technologies
Our research is powered by a host of different technologies.
MiniZinc 2.0
We are developing version 2.0 of the MiniZinc language and toolchain, featuring a completely redesigned compiler architecture, an integrated development environment (IDE), and a number of important additions to the MiniZinc modelling language. The compiler will be modular and embeddable, making it easy to integrate MiniZinc models and compatible solvers into application software and connect them to data sources and user interfaces. The IDE will make it easy to write, debug and experiment with MiniZinc models, as well as provide access to all of the advanced model analysis tools we develop. In terms of new language features, MiniZinc 2.0 has support for functional constraints, option types, generalised comprehensions and let expressions. These new features are carefully designed to enhance the expressivity of optimisation models and at the same time help the MiniZinc compiler to generate better code. A further planned extension will add support for enumerated types as well as syntax for expressing stochastic combinatorial problems.
Objective-CP
Objective-CP is an optimisation system that views an optimisation program as the combination of a model, a search, and a solver. Models in Objective-CP follow the modelling style of constraint programming and are concretised into specific solvers. Search procedures are specified in terms of high-level nondeterministic constructs, search combinators, and node selection strategies.Objective-CP supports fully transparent parallelisation of multi-start and branch & bound algorithms. The implementation of Objective-CP is based on a sequence of model transformations, followed by a concretisation step. Moreover, Objective-CP features a constraint-programming solver following a micro-kernel architecture for ease of maintenance and extensibility. Experimental results show the practicability of the approach. We will develop plug-in modules extending the Objective-CP micro-kernel to incorporate state-of-art learning capabilities, and specific modelling and solving capabilities for important application areas such as scheduling and packing.
Research Projects
We have a number of ongoing internal research projects.
Stochastic Modelling
Many real-world optimisation problems have to deal with uncertainty, such as uncertain demand or uncertain amount of resources. These uncertainties needs to be taken into account to provide good, realistic solutions. However, formulating and solving problems with uncertainty is a challenging task, and current technology prevents non-expert users from employing stochastic optimisation techniques. Our aim is to reduce this bottleneck by providing a high-level modelling language for uncertainty (an extension of MiniZinc) that allows the user to declaratively state the problem in a natural way without having to commit to (or having any knowledge of) a solving technique. The underlying system performs model enhancements and transformations if necessary, and can assist the user in taking stochastic modelling decisions, such as formulating recourse.
Language of Learning
Constraint programming solvers which learn nogoods are an exceptionally efficient tool for solving a wide range of problems. But sometimes they cannot compete with other simpler approaches (such as translation to SAT solving) because they do no introduce the intermediate literals appearing in a SAT decomposition. Critical to the effectiveness of learning is the language which is available to learn on. We need to generate hybrid methods that introduce intermediate literals that allow use to learn important reusable information. In this project we develop theory and methodologies to automate this process using techniques such as lazy decomposition and structure based extended resolution.
Global Model Analysis
We are working on automatic as well as interactive techniques that analyse and improve models of optimisation problems. These pre-solving and analysis techniques take advantage of the rich model structure available through the MiniZinc modelling language. For example, we can analyse a model to detect constraints for which dedicated formulations (so called global constraints) are available. Other techniques are based on hybridisations, taking advantage of the inference power of one solving technique to improve the translation of a model for a different solving technique. This project will enable users to write more high-level models, and to get interactive feedback that helps them improve their models. Finally, the translation from a high-level to a low-level, solver specific formulation of a problem results in faster solving and better scalability.
Symmetry and Dominance Analysis
Symmetries occur frequently in combinatorial problems and handling them correctly can massively speed up the search for solutions. Dominance relations in optimisation problems can be similarly exploited. However, recognising that symmetries and dominance relations exist in a problem is very challenging, even for expert modellers. By complex analysis of models we can automate the recognition of symmetry and dominance, and then exploit this these properties when solving the problem.
Complex Scheduling and Packing
Solving complex scheduling and packing problems is a very challenging task due to their size and requirements on solutions. Current solution methods either do not scale up to large-size problems or provide not-good-enough solutions. Our goal is to investigate hybrid solution methods and techniques, which work well on large-scale problems and are able to model the problems in more detail.
Community Activities
MiniZinc Challenge
The MiniZinc Challenge compares different solving technologies for solving the same combinatorial problems. It drives the development of efficient solving technology, collects a set of challenging and interesting combinatorial benchmark problems, illustrates the comparative strengths and weaknesses of different solving technologies, and creates a well supported standard for modelling combinatorial problems.
Lightning Modeling & Solving Competition
In 2013 we ran the first Lightning Model and Solve competition, where teams compete to create solutions to 6 new combinatorial problems within a few hours. The event provides a challenging and entertaining diversion from the main conference, but also stress tests both the modelling and solving ability of the participants, and the effectiveness of the modelling and solving tools they choose to use.
Collaborations
The platform team has strong collaborative research relationships on solving technology with the University of Connecticut, Katholieke Universiteit Leuven, University of Newcastle, Zuse Institute Berlin, Technische Universität Berlin, KTH Royal Institute of Technology Stockholm, and École des Mines de Nantes. The platform project underlies all the other projects in optimisation at Data61 and we expect strong collaboration with the other research projects and their partners.
Previous post:
Coming up next: