Modelling
Modelling is a very broad concept, that can be used both for the statement of the problem in some formalism, and for the design of algorithms to solve the problem. We distinguish the conceptual model, which is a formal statement of the problem, from the design model, which specifies the algorithm to solve the problem.
The process of solving LSCO problems can be separated into creating the conceptual model, and an algorithm development process for mapping the conceptual model to a design model. This depends upon a language for writing conceptual models, and usually another language for writing design models.
For a platform that only uses MIP the language for writing design models need only be able to express MIP algorithms. For example mathematical modelling languages such as Gams and AMPL can express linear and integrality constraints, and a limited set of algorithm and search control facilities.
Constraint programming supports a much wider set of behaviours, based on local and tree search, and on a rich language of constraints which typically operate by pruning values for variables. CLP supports both conceptual modelling and design modelling for the CP solving paradigm. CLP systems include ECLiPSe, SICStus, CHIP and Mozart.
Restricting the algorithms to local search, makes it possible to define languages for expressing design models (such as the Localizer and Salsa languages) which cover a wide range of local search algorithms.
G12 will not only need provide a modelling interface to distinct techniques from MIP, CP and local search, but will also need to provide a modelling and mapping interface to methods for integrating these techniques and to algorithms that combine them. The design models for such an integrated scheme may involve combinations of algorithms from all three areas. The language in which the design models are expressed must therefore subsume the expressive power of all the above languages. Much more is required however, since the interactions between local search and `branch-and-infer' search opens a huge space of possible hybridisations.
Modelling real problems requires much more than just specifying the constraints and cost function. The user needs to be able to specify requirement for robust, as well as optimal, solutions. Moreover real solutions often need to be repaired when they are put into practice (for example a solution to a scheduling problem often needs to be changed in response to delays and machine breakdowns). It must be possible for the modelling language to specify the required type of robustness. Thirdly, for real-time problems, the need for a guaranteed response within a certain time may be an integral part of the problem statement, and must therefore be reflected in the model.
In order to maintain clarity, flexibility, simplicity and correctness, we will separate the conceptual modelling language from both the design modelling language and the search language.
The best starting point for a universal conceptual modelling language is a purely declarative modelling language. Such a language allows the modeller to give a high-level specification of the constraint problem in terms natural to the problem itself. In order to do so it must include data structures that naturally arise in modelling such as arrays and sets, as well as be extensible in order to incorporate new problem specific structures such as jobs and tasks. We need natural constructs for specifying large constraints and large conjunctions of constraints. In order to encapsulate common problem structure we need to be able to specify predicates and functions in the modelling language for reuse. A powerful modelling tool is the ability to `reify' a constraint, that is treat a constraint as a function that returns 1 if the constraint holds, or 0 otherwise. This facility must be available in the language. Finally the declarative modelling language must be a `meta-language', able to specify models for classes of problems, where the actual problem data is taken as an input.
We will develop a declarative modelling language independent of any particular solving technology in order to concisely and precisely express constraint problems. There are many challenges in the design of such a language. For example, how can we make the language suitable for both an operations researcher experienced in using restricted mathematical modelling languages such as Gams and AMPL, as well as computer scientists used to the flexibility and power of full programming languages. Naively adding feature upon feature to such languages leads to an unusable mess, so we must define orthogonal language constructs that work together seamlessly. We need to avoid the traps of existing conceptual modelling languages that are tightly tied to the design modelling languages they support.
Our aim is to build a language that can be grasped piece by piece, according to the needs of the user. Moreover, each construct in the language must be justified in terms of the power and economy offered to the user. The effort expended in understanding the construct must pay back thousandfold in its utility.