| AITEC Contract Research Projects in FY1998 : Proposal |
| Principal Investigator : | Dr. John DARLINGTON, Professor |
| Department of Computing, Imperial College |
Applying constraint logic programming languages for modelling multi-objective decision making under uncertainty
Quantitative modelling is now recognised as the key technology underlying decision support in financial, commercial and industrial organisations. However, despite important advances, the practical adoption of this technology has been limited. We identify two major deficiencies that have led to this. Firstly the limitation of the classical approach has been one of modelling. Both the specification and analysis of the solution of real world problems are highly complex. Hence, non-specialist potential users, such as managers, are discouraged from formulating the problem or interpreting the results. Secondly, progress has been limited by the lack of effective algorithms to address some of these problems and the absence of good high performance computing platforms to compute solutions reasonably rapidly.
In the first phase of the project (1997-1998), we have developped a prototype of a logic specification language for multi-objective decision support. We developped also a system for translating the logical specification into a mixed integer programming problem. We have also tested the specification using some real world application examples including the bond portfolio problem suggested in the proposal. A prototype system has been implemented using Sicstus Prolog. We have also implemented a highly efficient IP (Integer Programming) Solver based on an improved Buchburger algorithm. This new algorithm provides a new methodology to solve stochasic integer programming problems.
Multi-objective decision problems arise naturally in management and financial decision making among a wide range of industrial sectors. Problem specification can often be facilitated and made flexible by allowing the decision maker to specify the overall problem at a high level in terms of qualitative logic-based conditions that either define the constraints or indicate the relative preferences between the multiple objectives. This preference structure is often altered interactively, as the user develops the model. The proposed project involves applying constraint logic programming technologies to develop a natural problem specification framework for large scale multi-objective decision making under uncertainty. This tool will enable decision makers to define, control and refine the whole decision making procedure through a user oriented and declarative modelling mechanism. This project will also investigate a new method for supporting decision making within a stochastic environment.
The proposed project involves the application of constraint logic programming technologies to build up a modelling tool for large scale multi-objective decision problems under uncertainty. The distinct advantage of the CLP specification lies in its declarative nature and the flexibility of abstraction, thus enabling operations research to be effectively applied to real world applications. A CLP specified decision model can then be translated into constraints involving binary integer variables and the resulting stochastic integer programming problem solved using parallel constraint solvers.
The major components of the proposed integrated and holistic solution to the modelling problem will comprise ---
A CLP based framework that allows the natural specification of complex modelling and decision making procedures. The modelling language will adopt CLP syntactical conventions but will be extended with language constructs for specifying uncertainty using a scenario based mean-variance framework. A prototype of this modelling framework has been built in the first phase of the project.
A methodology for translating such logic-based specifications into an integer programming formulation. The translation method is based on the correspondence between first order logic and mixed integer problems (MIP), which have been investigated in the mathematical programming community by Hooker, Grossmann and Williams. For example, Hooker presented a close correspondence between logic inference models such as the Davis-Putnam procedure and resolution with the constraint solving algorithms in MIP, Branch and Bound and Cutting-planes. In the first phase of the project, we have explored this correspondences based on McKinnon and Williams' approach which transforms a logic specification into MIP problems with inequality constraints.
The modelling language will interface with a set of parallel constraint solvers. The generated constraints will be solved using underlying constraint solvers. New constraint solvers for stochastic IP will be developed based on the novel algebraic IP solver developed in the first phase of the project.
The whole system will be developed to facilitate incremental expansion. An open interface to a wide range of constraint solving algorithms for interrelated integer programming algorithms will be provided using the API (application program interface) technique.
A WWW-based interface to support easy system deployment. Using Java Applets the logic based modelling language will be available via the Web. This will provide a platform independent client tool for decision makers. The solvers will run on a high performance server. Using this Java enabled Web-based client-server model, the power of high level modelling and high performance constraint solving can be integrated and deployed for a wide range of business users to solve large scale multi-objective decision making problems.
| | Name | Affiliation |
|---|---|---|
| Principal investigator | John Darlington | Imperial College |
| Collaborating researchers |
Yi-ki Guo | Imperial College |
| Berc Rustem | Imperial College |
The modelling language is based on CLP syntactical conventions. Mathematical relations will be modelled using algebraic constraints. A complete logic statement will be translated into a formula in a mixed integer programming setting. The translation algorithms will be based on Hookers and Williams' methods of relating logic formula with formula in mathematical programming. This is a non-trivial research subject. In particular, we plan to investigate the effective way to represent uncertainty within the logic framework and its translation. Uncertainty will be specified by developing novel IP solvers.
Logic Modelling Language for Multi-Objective Decision Support (LML)
The software is a CLP-based modelling language for large scale multi-objective decision making. The language provides a logic based specification of multi-objective optimisation problems. Symbolic relations as well as interactive features of multi-objective optimisation is uniformly modelled by applying symbolic logic and mathematical relations are specified naturally using algebraic constraints. The language is a specification language rather than a general purpose constraint logic programming language. It is designed to specify multi-objective decision making problems under uncertainly based on the stochastic linear/integer programming method. A logically specified model will be translated into a stochastic integer problem which can be solved directly by integrated stochastic IP solvers. The system is also equipped with the interface to a set of constraint solvers including the novel parallel stochastic IP solver which will be developed in the project.
The software comprises a Web-based user interface enabling users to access the modelling language, a model language with a translation system to translate logic formula into a mixed integer problem and an interface to a set of parallel constraint solvers. The interface as well as the translation system will all be implemented in Java togther with a symbolic rewriting language such as Mathematica to fully explore the advantages of object oriented programming and symbolic computing.
One of the major improvement of the functionality of the software will be achieved by developing a novel stichastic IP solver. This functionality provides the key support to the multi-objective decision support under uncertainty. Solving stochastic IP is computational intensive. Thus, parallel computing technology will be employed to tackle the complexity.
The Web based user interface will be implemented in Jave. The CLP based modelling system will be implemented in a symbolic programming language such as Mathematica. The interface to the underlying solvers, which are coded in C and MPI, will be supported using Java inter-language communication facilities.
The expected size of the software is about 4 MB.
The expected users will include decision makers in a wide range of commercial and industrial sectors. The method of dissemination for the results and software developed will be via building up a prototype of a WWW-based decision support server supported by the parallel computing resource of IC Fujitsu Parallel Computing Research Centre. By providing a publicly accessible decision making environment, it is intended that the system would be promoted, improved and adopted by users as tools for their application.
The system provides decision makers with an interactive tool for defining, controlling and refining a decision support procedure. Together with the logic-based specifications, the framework will provide a tool for management which would be easily applicable, flexible and effective.