(5) Applying Constraint Logic Programming Languages for Modelling Multi-objective Decision Making under Uncertainty

[Contents]

1. Background of the research
2. Purpose of the research
3. Contents of the research
4. Project Organization/Research Method
5. Resulting Software

[Background of the research]

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.

Recent activity at Imperial College related to the above areas includes work on parallel methods for decision making under uncertainty, algorithms for discrete and continuous optimisation and parallel computing research. A set of efficient parallel algorithms have been developed for large scale decision support under uncertainty [1][2][3]. In order to exploit the power of these new algorithms for decision makers in real world applications, a declarative modelling system becomes necessary. We propose to develop such a system that would enable the specification of complex decision support procedures under uncertainty using CLP technologies. Constraint solving algorithms such as simplex algorithms for mixed integer programming problems, the interior point algorithm for the quadratic integer programming problem and the Geometric Gröbner base algorithm for parametric and stochastic integer programming problem will be integrated as built-in constraint solvers. Logically specified decision problems will be transformed into admissible constraints which will then be solved using the underlying optimisation algorithms on a parallel computer.

Selected Publications

[1] Darlington, J., Pantelides, C.C., Rustem, B. and Tanyi, B.A. (1996). An Algorithm for Constrained Nonlinear Optimization under Uncertainty. Research Report, Department of Computing, Imperial College (to be published in SIAM J. Optimization).

[2] Qiang Li, Yi-ke Guo, Tetsuo Ida and John Darlington (1997) The Minimised Geometric Buchberger Algorithm: An Optimal Algebraic Algorithm for Integer Programming. Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1997, Maui, Hawaii U.S.A. To appear.

[3] Pinto, R.L.V. (1995). A Logic Based Modelling Language and Integer Programming Framework for Multi-criteria Optimisation, PhD Thesis, Department of Computing, Imperial College.

[4] Pinto, R.L.V. and Rustem, B. (1994). Building and Solving Multi-criteria Models Involving Logical Conditions. Advances in Computational Economics (AICE), 123--136, Kluwer Academic Publishers, Dordrecht.

[5] Guo, Y. (1994). Definitional Constraint Programming. PhD Thesis, Department of Computing, Imperial College.

[Purpose of the research]

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.

[Contents of the research]

The proposed project involves the application of constraint logic programming technologies to build up a modelling tool for large scale multi-objective decision problems. 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 business model can then be translated into constraints involving binary integer variables and the resulting mixed integer linear programming problem solved using parallel constraint solvers.

The major components of the proposed integrated and holistic solution to the modelling problem will comprise ---

1. 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.

2. 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 our work, we will explore this correspondences based on McKinnon and Williams' approach which transforms a logic specification into MIP problems with inequality constraints.

3. The modelling language will interface with a set of parallel constraint solvers. The generated constraints will be solved using underlying constraint solvers that have been developed at Imperial College. These solvers include:
   
   • A Simplex Algorithm for solving mixed integer programming problems.
   • Geometric Gröbner base algorithms for solving parametric and stochastic integer programming problems.
   • An Interior Point Algorithm for solving quadratic integer programming problems.

4. 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.

5. 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.

[Project Organization/Research Method]