Conference heron::euro_swas_ai

294.0. "Charme School" by YIPPEE::MCGREGOR () Fri Mar 15 1991 17:03

As a follow-on of note 224, some more on Charme.
    
    Anyone have any other info to share on this?
    
    George
    
    
Constraint Language Programming (and BULL and IBM)
--------------------------------------------------

This report is a result of a trip to the University of Edinburgh on the
27,28 February and the 1 March 1991. There is another report which covers
Speech Technology aspects of this trip. 
This report is concerned with an approach to solving heavily constrained 
problems (eg. Operational Research problems), and specifically describes the 
threats posed by BULL and IBM in this domain, and how we should "position"
ourselves with respect to this threat.

Background
----------
I attended a training on "Programming with Constraints", a three day course.
This course turned out to be a "hands-on" training on Charme, with about
half-a-day on Constraint Languages (CL's) in general. This was an interesting
competitive update, since Charme is exclusively and agressively marketed by 
BULL. I got the chance to see some of Bulls promotional material during this
training.
The training was very good.


The History of Charme 
---------------------
Charme is the finite-domain part of CHIP, a constraint language produced
by the ECRC (a now defunct research collaboration of Siemens, ICL, Bull at
Munich). CHIP has 3 problem solvers, one for rationals, one for booleans,
and one for finite domains). See the book by P. van Hentenryck "Constraint
Satisfaction in Logic Programming". (MIT press)
    The basic idea is that "constraints help us
understand the search space, and search it more efficiently". Charme has 
been used with success in domains which were previously considered to be
Operational Research (OR).

The Charme Language
-------------------
Go to the next section if the technical details dont interest you!!!

Charme works with integers. Is written in C. Is interpreted. 
Some fundamental concepts:

1. Domain variable
Domain Variables are defined by the range of values they can adopt, and this is
modified as the program executes. "ordinary variables" exist too.

3. Backtracking
Charme problems are SEARCH problems, so if a choice fails backtacking occurs.
Values assigned to variables can only be "reassigned" by backtracking (as in
Prolog). backtracking can be instantiated by the user.
   
3. Constraint Propagation
A variable whose domain is being reduced may feature in constraints on
other variables. Checking these constraints can eliminate failures in
advance, and cut down on backtracking.

In Charme, constraints are put in place, using various syntactic constructs,
and then a generate call is made.

Here is the 8-Queens in Charme

define queens
{

/* An array of 8 domain variables, representing the columns   */
/* Each domain variable will acquire a value between 1 and 8 showing the */
/* Queens ROW position for the column					*/
/* Dont be confused by the different meanings of the ".." notation      */

   array Col::[1..8] of 1..8;

/* 1st constraint : none of the array elements can have the same value */

   all_diff (Col);

/* Now set up the constraints which exclude the queens being on the
   same diagonal  != Not equal */
 
   for I in 1..(N-1) do
   {
	for J in (I+1)..N do
	{
		Col[I] != Col[J] + (J-I);
		COL[I] != Col[J] - (J-I);
	}	
   }

/* Now generate a solution */

generate Col;
Print Col;

}

This generates solutions very rapidly. In fact I did some tests on some
crypto-arithmetic problems which are in the Prolog III paper, and 
Charme came out very favourably in terms of speed.

I have lots of documentation and other examples. There are a couple
of large timetabling examples in the documentation.  

The other important thing is a very straightforward syntax for defining
variables which should be optimised/minimised in a solution. The generate 
statement then keeps generating solutions until the optimal is reached. 
There are ways in which you can change how the generation works.






The Market
----------

This is as such a small market, but it should be noted that "resource 
allocation" problems tend to have a high visibility,
firstly because they are often critical to the business,
and secondly because OR approaches have often failed to deliver a solution.
So the leverage potential is high.

Another important point to note is that by their very nature, such problems
must be solved by tight integration with existing information systems (e.g.
process databases), which fits in with our integration strategy

The major commercially available products are as follows:

Charme from Bull, runs on UNIX, in principle NOT limited to Bull machines,
It ran on a Sun in Edinburgh.
(40 licenses worldwide in 1 year)

Chip from ICL, sold exclusively with consultancy. Not sure about licenses

CLP(R) from IBM, not sure about licenses sold. More of a research tool.

Prolog III from Prologia. Around 130 licenses sold? Runs on lots of
platforms.

Summary
----------

We are developing a very good relationship with Prologia, and should
propose Prolog III as a solution if a customer is specifically looking
for a constraint language. Prologia will help us in a competitive situation.

More detail in the EURO_SWAS_NOTES file on positioning Charme and Prolog III.
Serge Himbaut is the Valbonne Digital contact for Prolog III. You can get it 
across the net!

If Charme ran exclusively on Bull equipment, it wouldn't pose much of a threat,
but the fact that Bull are willing to sell on other platforms is more
worrying!


George