C o m p u t a t i o n a l    L o g i c Interval Constraint Solver For Microsoft Excel

 Interval Constraint Solver For Microsoft Excel Eero Hyvvonen The vision Spreadsheet computing is one of the true success stories of information technology. Millions of copies of ever fancier and larger systems are sold every year. However, their underlying mathematical idea of evaluating functions is still the same used already in VisiCalc in the late 70's! What if the old mathematical basis of spreadsheet computing could be made more useful to the millions of spreadsheet users? And as a loadable add-in extension for current commercial systems, such as Microsoft Excel? Early developments This question was asked at VTT Technical Research Centre of Finland after inventing the idea of interval constraint satisfaction (1) concurrently with some other groups in the 80's. The first experimental interval constraint spreadsheet system (2) was implemented in Lisp, but Microsoft Excel was soon selected as the host spreadsheet system as the market leader. Since then, C++ has been used as the programming language and environment for interval constraint satisfaction (3) in contrast to many other groups. Reasons for this were practical: The constraint software had to be integrated with other existing systems and had to be efficient. However, the marriage of interval constraint satisfaction with spreadsheet computing was not feasible, yet. The memory available with Excel under the 16-bit Windows operating system was simply not large enough and algorithms and hardware were much slower than today. Also Excel's macro language provided by Microsoft was not very flexible and was fairly slow. With the new 32-bit Windows 95 and Windows NT operating systems, and the Visual Basic macro language the situation rapidly changed. Range Solver for Microsoft Excel (4) was implemented. Interval Solver for Microsoft Excel released In summer 1997, the first commercial version of the system, renamed as Interval Solver for Microsoft Excel was released by Delisoft Ltd, a spin-off company of VTT. Interval Solver is the first implementation of interval constraint satisfaction on a commercial spreadsheet platform. Interval Solver is capable of evaluating Excel formulas written inside the =I(formula) function, such as =I(A1^2+SIN(A1)*B2-2) with interval-valued arguments. By using global interval optimization algorithms and cascaded function globalization (4), the actual value ranges are obtained without overestimation typical to classical interval arithmetic. Unlike in ordinary Excel, formula values can be bound with intervals. The user can also insert equation/inequality formulas, such as: =I(SIN(A1)+BI=A1^2*B1) =I(SIN(A1)+BI>A1^2*B1) The system interprets Excel formulae written inside the =I( ) form as a set of equation and inequality constraints, and solves them using interval constraint propagation (tolerance propagation) and interval analytic techniques. Algebraic techniques are used in order to make formulae more efficient for interval evaluations. Interval Solver can either bound all solutions of the constraints, or determine individual solutions down to user given precision. It currently consists of over 100.000 lines of code. Interval Solver for Microsoft Excel add-in is available though Internet. A free Evaluation Kit of the system together with additional material can be downloaded at: http://www.delisoft.fi/ExcelProducts/IntervalSolver/ References 1. Hyvvonen, E. (1989) Constraint reasoning based on interval arithmetic. Proceedings of IJCAI-89, Detroit, pp. 1193-1198. 2. Hyvvonen, E. (1991, 1994) Interval constraint spreadsheets for financial planning. Proceedings of the 1st International Conference on Artificial Intelligence Appliciations on Wall Street. IEEE Press, New York, 1991. Refined version published as: Hyvvonen, E.: Spreadsheets Based on Interval Constraint Satisfaction, Artificial Intelligence for Engineering Design, Analysis, and Manufacturing 8, 1994, 27-34. 3. Hyvvonen, E., De Pascale, S. (1995) InC++ library family for interval computations. International Journal of Reliable Computing, supplement, Proceedings of Applications of Interval Computations, El Paso, Texas, USA, 1995. 4. Hyvvonen, E., De Pascale, S. (1996) Interval computations on the spreadsheet. In: B. Kearfott, V. Kreinovich (Eds.) Applications of Interval Computations, Kluwer, New York, 1996, 169-210. Delisoft Ltd Urho Kekkosen katu 8 C 30 FIN-00100 Helsinki, Finland Tel. +358 9 6866550 Fax + 358 9 68665544 http://www.delisoft.fi/

 [ ERCIM Working Group on Constraints ] [ The LLC group at ENS Paris ] [ Interval Constraint Solver For Microsoft Excel ] [ Scheduling Sport Tournaments using Constraint Logic Programming ]