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

Title of the Research Project, Principal Investigator

(1) Title of the Research Project

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

(2) Principal Investigator

John Darlington, Professor
Imperial College/ Fujitsu Parallel Computing Research Centre

Contents

(1)Overview

The goal of the research in this period of time is to investigate the application of constraint logic programming technologies to build up a modelling tool for large scale multi-objective decision problems. The research activities include:

• Evaluate the possibility of using existing CLP languages such as CLP(R), CAL and GDCC.
• Design a CLP-based logic modelling language.
• Test the language by modelling a concrete optimisation problem such as the bond portfolio problem in financial engineering.
• Develop and investigate a set of solvers for multi-objective decision problems.

Progress has been made in these research activities.
We have developed the technology of specifying a class of multi-objective problems in terms of logical constraints.

A prototype of the Logic Modelling Language for Multi-Objective Decision Support (LML) is under design.
We also investigating the mechanism to translate logic specifications of multi-objective problems into IP (Integer Programming Constraints). We have also investigated the possibility of applying existing CLP languages in particular the CAL language and GDCC developed in ICOT during the fifth generation computer project. We have developed a novel IP solver based on the Buchburger algorithm. The experimental implementation (both sequential and parallel) of the new IP solver proved its feasibility for real world applications.
This new development sets up the path of applying CAL and GDCC, where the Buchburger algorithm has been built in to the languages as the constraint solvers, for modelling multi-objective problems.

These activities and achievement have laid down a solid foundation for the next stage of development of a CLP based modelling system for multi-objective optimisation.

(2) Designing a Logic Modelling Language for Multi-Objective Decision Support

We are intensively investigating logic modelling systems for multi-objective optimisation. In particular, we have developed a simple LML language based on the pure first order logic and arithmetic constraints. This work is based on the early work of Dr. Rodrigo Pinto [1]. developments have been made in the design of the syntax of the language, the mechanism for specifying multi-objective decisions ( mathematical and outranking method), the 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. These case studies have provided useful feedback on how to improve the design of the specification system. It also provides us valuable ideas on how to applying existing CLP languages for specifying multi-objective optimisation problems.

(3)Solving Integer Programming based on Buchburger Algorithm

Conventional methods for solving integer programming are based on searching algorithms where heuristics such as branch and bound are applied to reduce the search space.
Recently, various algebraic IP solvers have been proposed based on the theory of Gröbner bases.
The key idea is to encode an IP problem IPA.C into a special ideal associated with the constraint matrix A and the cost (object) function C. An important property of such an encoding is that its Gröbner basis corresponds directly to the test set of the IP problem. The main difficulty of these new methods is the size of the Gröbner bases generated. In the proposed algorithms, large Gröbner bases are caused by either introducing additional variables or by considering the generic IP problem IPA.C . With a co-operation with the researchers in University of Tsukuba, 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) [2] and Thomas's truncated GBA [3]to achieve a very efficient and general IP solver. We have implemented the system and also carried out experiments to compare this algorithm with others such as the geometric Buchburger algorithm, the truncated geometric Buchburger algorithm, and the algorithm in GRIN. These experiments show that the new algorithm offers significant performance improvement. The experiment results are listed as the following table:

Problem	Entries	MGBAS		GBAS		TGBAS		GRIN
		Size	Time	Size	Time	Size	Time	Size
mat3x7.1	0-20	17	0.46	568	1462.96	272	55.96	31
mat4x8.1	0-20	157	25.91	24	3509.3	2352	447.68	294
mat4x8.2	0-20	112	17.82	74	638.2	1640	335.76	205
mat4x8.3	0-20	251	54.84	38	1599.4	3848	783.44	481
mat5x10.1	0-4	121	31.53	00	0307.6	1632	335.24	204
mat5x10.2	0-4	142	90.56	69	2095.3	2800	559.60	350
mat5x10.3	0-4	112	63.69	74	638.4	3312	671.52	414
mat6x12.1	0-3	134	121.7	47	3531.1	4467	895.36	561
mat6x12.2	0-3	103	89.87	44	862.07	3304	671.52	413
mat6x12.3	0-3	267	278.3	92	2975.5	5672	1119.20	709
mat8x16.1	0-1	87	7.67	5	520.44	568	121.84	126
mat8x16.2	0-1	101	12.53	6	857.29	650	135.89	168

This work suggested that it is possible to use directly some existing CLP languages such as CAL and GDCC where the embedded constraint solvers are based on computing Gröbner base. We consider this development as an important achievement of the project. We are now working on the extension of the system to the mixed integer programming. We are planning to complete this work by the end of the year.

(4)The Next Stage of Development

The next stage of the development (Jan 1998 -- Mar 1998:) will include the further investigation of the mechanism of translating the logic specification into a mixed integer problem and implement the prototype using the newly developed algorithm. A first year report will be delivered to report on the design and prototype implementation by the end of March 1998. In addition, we will intensively investigate the application of CAL or GDCC for multi-objective optimisation.

References

[1]RODRIGO PINTO Logic Based Framework of Multi-objective OPtimisation Ph.D Thesis, Dept. of Computing, Imperial College, 1995

[2]S.HOSTEN, and B.STURMFELS. GRIN: An implementation of gröbner bases for integer programming.
In Integer Programming and Combinatorial Optimization (1991), E. Balas and J.Clausen, Eds., LNCS 920 Springer Verlag, pp.207--276.

[3]R.R.THOMAS.A geometric buchberger algorithm for integer programming. Mathematics of Operations Research 20, 4 (Novermber 1995).