Applying Constraint Logic Programming Languages for Modelling Multi-objective Decision Making under Uncertainty (Summary of Research Results) (Aug. 1998 -- Feb 1999)

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.

We have completed successfully the project with the following achievements:

• We have developed a powerful 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 a system of translating the logical specification into a mixed integer programming problem. A prototype system has been implemented using Sicstus Prolog and mathematica. The correctness of the system is also proved.

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

• We applied this new algebraic algorithm to solve a class of stochasic integer programming problem, called chanced constrained integer programming (CIP), where uncentainty of a decision problem is given by stating the constraints with probabilities. Chanced constraint integer programming is a very challenging reserach subject where tradinational IP solving mechanisms fail to provide efficient solutions. We have implemented a CIP solver based on the MGBA which provides a promising method for solving CIP problem.

• We also delevopped a Web interface to the whole system to enable the input of logical specification from the Web across the internet.