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/ |