Applying Constraint Logic Programming Languages for Modelling Multi-objective Decision Making under Uncertainty (Summary)
(Aug. 1996 -- Feb 1997)

John Darlington - Yike Guo

Imperial College/ Fujitsu Parallel Computing Research Centre

This project aims to develop a modelling tool for large scale multi-objective decision problems by applying constraint logic programming technologies. The distinct advantage of the logical 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 concrete research subjects of the project include:

1. A logic based framework to support the natural specification of complex modelling and decision making procedures. The modelling language is designed based on CLP language convensions butwill be extended with language constructs for specifying uncertainty.

2. A methodology for translating such logic-based specifications into an integer programming formulation.

3. The modelling language will interface with a set of parallel constraint solvers including:
   • 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. A WWW-based interface to support easy system deployment.

The whole project started in Aug. 1997. Thus, we have in fact only 6 month for research and development when we write this report. However, in this very short period of time of the project, we have made significant progress:

• We have been intensively investigating logic modelling systems for multi-objective optimisation. In particular, we have developed a powerful CLP-based logical modelling language where pure first order logic and arithmetic constraints are used to specifying multi-object deciision support problems. This work is based on the early work of Dr. Rodrigo Pinto, McKinnon and Williams. We developped also a system of 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 propose a new algebraic algorithm for solving integer programming problems. based on the Buchburger algorithm. The new algorithm, called the Minimised Geometric Buchburger Algorithm (MGBA), combines various newly developed symbolic IP solvers such as Hosten and Sturmfels method(GRIN) and Thomas's truncated GBA to achieve a very efficient and general IP solver. A prototype system has also been implemented.

In this report, we summarise the research and the development results in this period of time. We will also present the plan for the research and develoment in the next phase of the project.

• Developping a Logical Specification System for Multi-Objective Decision Support
  • Background
  • Transforming Logical Specification into IP
• Developping Generic Symbolic IPSolver
• Conclusion and the Future Work