CIAL: An Interval Constraint LP Language

Keywords: constraints.

CIAL is an interval constraint LP language. The main difference between CIAL and other CLP(Interval) languages is that a linear constraint solver, which is based on preconditioned interval Gauss-Seidel method, is embedded in CIAL in addition to the interval narrowing solver.

The main motivations for a linear solver are:

Pure interval narrowing fails to narrow the intervals to any useful width even for such simple systems as {X+Y=5, X-Y=6}. Interval splitting may help but is costly.

Pure interval narrowing cannot always detect inconsistency or halt (in a reasonable time). A simple example is {A+1=D, A+B=D, A > 0, B < 0}.

Efficient linear constraint solver is also important to the study of efficient non-linear constraint-solving. Recent results show that interval Newton method works better than pure interval narrowing for solving non-linear constraints, but may require to solve many linear constraints in order to give the best results.

This version of CIAL prototype is implemented as an extension to CLP(R) v1.2 and tested on Sun Sparc machines. You should have obtained CLP(R) from IBM prior to installing CIAL. Please contact joxan@watson.ibm.com for further enquiries regarding CLP(R). Our distribution is in the form of patches to the CLP(R) sources.

If you are interested in obtaining CIAL, please send a request to:

Jimmy Lee
Dept. of Computer Science
The Chinese University of Hong Kong
Hong Kong
Email: cial@cs.cuhk.hk