Abstract
We introduce a generalization of the spreadsheet paradigm, called Knowledgesheet, for solving a class of constraint satisfaction problems. The traditional spreadsheet paradigm is based on attaching arithmetic expressions to individual cells and then evaluating them; our Knowledgesheet interface instead allows finite domain constraints to be attached to individual cells that are then solved to obtain a solution. This extension provides an easy-to-use interface for solving a large class of constraint satisfaction problems—those whose specification and solution conforms to a 2-dimensional structure, e.g., scheduling problems, timetabling problems, etc. A prototype for the Knowledgesheet has been developed and applied to solve many different types of problems.
The authors have been partially supported by NSF grants CDA 97-29848, CDA 98-02251, CCR 99-00320, CCR 99-04063.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Van Hentenryck, P., Constraint Satisfaction in Logic Programming, The MIT Press, Cambridge, MA, England, 1989.
Marriott, K., and Stuckey, P. J., Programming with Constraints: An Introduction, The MIT Press, Cambridge, MA, England, 1998.
Cohen, J., Logic Programming and Constraint Logic Programming, The Computer Science and Engg. Handbook, pp. 2066–2093, CRC Press, Inc., Florida, US, 1996.
H.-J. Goltz and D. Matzke. University Timetabling Using Constraint Logic Programming, Proc. PADL’99, Springer LNCS 1551, 1999.
G. Gupta and S. F. Akhter. Knowledgesheet: A Spreadsheet-based Interface for Interactively Solving Scheduling Problems. Patent pending. Feb. 1999.
Boizumault, P., Delon, Y., and Peridy, L., Constraint Logic Programming for Examination Timetabling, The Journal of Logic Programming, pp. 217–233, 1995.
Sterling, L., and Shapiro, E., The Art of Prolog, The MIT Press, 1994.
Meier, M., ECLiPSe User’s Manual, IC-PARC Tech. Rep., 1997.
S. F. Akhter. Knowledgesheet: A User-Interface for Solving Constraint Satisfaction Problems. Master’s thesis. New Mexico State University, July’ 98.
Henz, M., and Würtz, J., Using Oz for College Timetabling, In proceedings of the 1995 Int’l Conf. on Automated Timetabling, Edinburgh, Scotland.
Colorni, A., Dorigo, M., and Maniezzo, V., Metaheuristics for High-School Timetabling, Computational Optimization and Applications, 9(3): 277–298, 1998.
Renschler, M., Configuration Spreadsheet for Interactive Constraint Problem Solving, Conference Proceeding, Proc. Practical Applications of Constraint Tech., 1998.
Lai, K., Malone, T.,W., and Yu, K., Object-Lens: A “Spreadsheet” for Cooperative Work, ACM Transactions on Office Information Systems, 6(4): 332–353, 1998.
Yoder, A., G., and Cohn, D., L., Real Spreadsheets for Real Programmers Proc. International Conference on Computer Languages, IEEE, pp. 20–30, 1994.
Hofe, H., M., ConPlan/SIEDAplan: Personnel Assignment as a Problem of Hierarchical Constraint Satisfaction, Conference Proceeding, PACT 97, pp. 257–271.
Shvetsov, I., Kornienko, V., and Preis, S., Interval Spreadsheet for problems of financial planning, Conference Proceeding, PACT 97, pp. 373–385.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gupta, G., Akhter, S.F. (1999). Knowledgesheet: A Graphical Spreadsheet Interface for Interactively Developing a Class of Constraint Programs. In: Pontelli, E., Santos Costa, V. (eds) Practical Aspects of Declarative Languages. PADL 2000. Lecture Notes in Computer Science, vol 1753. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46584-7_21
Download citation
DOI: https://doi.org/10.1007/3-540-46584-7_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66992-0
Online ISBN: 978-3-540-46584-3
eBook Packages: Springer Book Archive