by Antonio Frangioni and Luis Perez Sanchez
The I-DARE system aims at helping practitioners to bridge the gap between mathematical models cast in their natural form and the myriad of available specialized solvers capable of exploiting the valuable, but possibly hidden structures in the model. It does this by automating the search for the best combination of (re)formulation, algorithm and parameters (comprising the computational architecture), until now a firm domain of human intervention.
Complex, hierarchical, multi-scale industrial and natural systems generate increasingly large mathematical models. Practitioners are usually able to formulate such models in their ‘natural’ form; however, solving them often requires finding an appropriate ‘reformulation’ to reveal ‘structures’ in the model which make it possible to apply efficient, specialized approaches. The search for the ‘best’ formulation of a given problem, the one which allows the application of the algorithm that best exploits the available computational resources, is a painstaking process requiring considerable work by highly skilled personnel. Experts in solution algorithms are required to figure out which pair (formulation, algorithm) is best, considering issues like the appropriate selection of the several obscure parameters of each algorithm.
We aim to improve the average effectiveness and efficiency of this search in the (formulation, solver, configuration) <f,s,c>-space by developing a software system capable of automating its main steps. The I-DARE system is divided into three main parts: Front-End (FE), Core System (CS) and Solving Section (SS).
The FE part comprises one or more graphical and/or textual FEs for the system. A general Modelling Environment Handler (ME-Handler) declares all functionalities that I-DARE exposes to each modelling environment, setting the interface between the FE and the CS. The interface relies on I-DARE(im), a logic-based intermediate modelling language designed using Frame Logic (Flora2), which offers high deduction power with which to analyse (query) the models.
The CS is further subdivided into three components: formulation and reformulation, performance evaluation and control. The formulation component, denoted ‘Structures and ARRs’, is responsible for the definition of the structured model and of the corresponding structured instance, together with the set of reformulation rules. I-DARE(lib) is the package containing all the structures that I-DARE knows. A formulation complemented with actual data becomes an ‘Extended Model’; the Instance Handler (I-Handler) allows data to be retrieved from different sources. A general deduction system, I-DARE(t), can then be used to reformulate EMs by using the database ‘ARR’ of Atomic Reformulation Rules.
The performance evaluation component, denoted ‘ML’, is responsible for predicting the performances of each algorithm (considering its parameters) on a given reformulation of a given instance. This is a difficult task, for which different general-purpose and/or specialized Machine Learning approaches can be used, all implementing an abstract General Machine-Learning Control (GMLC) interface. Provided that the possible solvers for a given structure are not too many, an effective ML approach would provide the tools for performing the search in the <s, c> subspace, leaving ‘only’ the (re)formulation space to be explored. Other fundamental subcomponents of this component are the Continuous Learning mechanism which updates the knowledge base using all the outcomes of the solutions of the system, and the Meta-Learning mechanism that makes it possible to evaluate and compare different ML techniques.
The control component is composed of the package I-DARE(control), in charge of guiding the search for the best <f,s,c> triple. This package defines the abstract interface that any control mechanism will have available to guide the deduction process of I-DARE(t) for generating the tentative reformulations; the performances will be predicted by GMLC, until the desired <f,s,c> is reached.
The final part of the I-DARE system, the Solving Section, is responsible for applying the solution method on the chosen (re)formulation, and collecting and presenting the results to the CS, which will in turn refactor them in the format of the original instance to present them to the FE. Its interface with the CS is the I-DARE Enhanced Instance format, itself composed of three <f,s,c> parts. The I-DARE(solve) package will activate the process relying on the available set of Solver Handlers (S-Handler), ie implementations of the general solver interface that allows specific solvers to be plugged into the I-DARE system.
Figure 1: I-DARE architecture.
The implementation of the I-DARE system means dealing with deep and challenging issues: the development of a general formal definition of a notion of ‘best reformulation’ capable of expressing the different forms that are useful to practitioners, comprising those that cannot be obtained by application of simple syntactical rewriting rules; the development of a language that can be used to formulate large-scale ‘structured’ models and the reformulation rules that allow one model to be transformed into a different one; the development of practical algorithms for searching the <f,s,c>-space; the design of a general interface for numerical solvers which is capable of accommodating and exploiting structural information; and finally, the implementation of all the above into a coherent and functional software system, providing proof that an industrial-strength system is eventually possible.
Tackling these challenges can potentially have profound, lasting and disruptive effects on many facets of the development and deployment of mathematical models and the corresponding algorithms to solve them. While at the beginning the system targets a narrow set of structures, mostly coming from decision and optimization problems, it is conceptually open to integration of different sets of mathematical components from almost all fields of human speculative and practical activities. Proving that it is possible to streamline systems and to automate the exploitation of scientific and technological advances through the use of sophisticated ICT tools has the potential to bring about a true scientific breakthrough.
Links:
http://compass2.di.unipi.it/TR/Files/ TR-09-13.pdf.gz
http://compass2.di.unipi.it/TR/Files/ TR-09-18.pdf.gz
Please contact:
Antonio Frangioni
Dipartimento di Informatica, Università di Pisa, Italy
E-mail:
Luis Perez Sanchez
Dipartimento di Informatica, Università di Pisa,
