×

A canonical form for generalized linear constraints. (English) Zbl 0745.90046

Summary: The integration of the constraint solving paradigm in programming languages raises a number of new issues. Foremost is the need for a useful canonical form for the presentation of constraints. In the context of an extended class of linear arithmetic constraints we develop a natural canonical representation and we design polynomial time algorithms for deciding solvability and generating the canonical form. Important issues encountered include negative constraints, the elimination of redundancy and parallelism. The canonical form allows us to decide by means of a simple syntactic check the equivalence of two sets of constraints and provides the starting point for a symbolic computation system. It has, moreover, other applications and we show in particular that it yields a completeness theorem for constraint propagation and is an appropriate tool to be used in connection with constraint based programming languages.

MSC:

90C05 Linear programming
68W30 Symbolic computation and algebraic computation

Software:

GHC
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Adler, I., Equivalent Linear Programs (1976), Department of Operations Research, University of California at Berkeley, Technical Report
[2] Borning, A., The programming language aspects of THINGLAB-a constraint oriented simulation laboratory, ACM Transactions on Programming Languages and Systems, 3, 252-387 (1981)
[3] Bradley, C. H., Equivalent integer programs and canonical problems, Management Science, 17, 354-366 (1970) · Zbl 0213.44701
[4] Bledsoe, W. W., A new method for proving certain Presburger formulas, (Advance Papers 4th Int. Joint Conference on Artificial Intelligence. Advance Papers 4th Int. Joint Conference on Artificial Intelligence, Tibilisi, Georgia, USSR (1975)), 15-21
[5] Davis, E., Constraint propagation with integral labels, AI Journal, 32, 281-331 (1987) · Zbl 0642.68176
[6] Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, AI Journal, 34, 1-38 (1988) · Zbl 0643.68156
[8] Dobkin, D.; Lipton, R. J.; Reiss, S., Linear programming is log-space hard for \(P\), Information Processing Letters, 8, 96-97 (1979) · Zbl 0402.68042
[9] Kohler, D. A., Translation of a Report by Fourier on his work on Linear Inequalities, Opsearch, 10, 38-42 (1973), (Partial English translation in:
[10] Fiedber, S.; Inset, A.; Spence, L., Linear Algebra (1979), Prentice-Hall
[11] Fox, M., Constraint-Directed Search: A Case Study of Job-Shop Scheduling (1987), Morgan-Kaufmann · Zbl 0702.68032
[12] Grünbaum, B., Convex Polytopes (1967), Interscience, Wiley · Zbl 0163.16603
[13] Jaflar, J.; Lassez, J. L., Constraint logic programming, (Proceedings of POPL. Proceedings of POPL, Munich (1987))
[14] Jafar, J.; Michaylov, S., Methodology and implementation of a CLP system, (Proceedings of the 1987 Logic Programming Conference (1987), M.I.T. Press: M.I.T. Press Melbourne)
[15] Karmakar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 141-158 (1984)
[16] Karwan, M. H.; Lofti, V.; Telgen, J.; Zionts, S., Redundancy in Mathematical Programming, A State-of-theArt Survey, Lecture Notes in Economics and Mathematical Systems, 206 (1983)
[17] Khachiyan, L. G., Soviet Mathematics Doklady, 20, 191-194 (1979), English translation: · Zbl 0414.90086
[18] Lassez, J.-L.; Huynh, T.; McAloon, K., Simplification and elimination of redundant arithmetic constraints, (Proceedings of NACLP 89 (1989), MIT Press)
[19] Lassez, J.-L.; Maher, M.; Marriott, K., Unification revisited, (Minker, J., Foundations of Deductive Databases and Logic Programming (1988), Morgan-Kaufmann) · Zbl 0645.68046
[20] Lassez, J. L.; McAloon, K., Applications of a canonical form for generalized linear constraints, (Proceedings of the 1988 FGCS Conference. Proceedings of the 1988 FGCS Conference, Tokyo (1988)), 703-710
[21] Lassez, J.-L.; McAloon, K., Independence of negative constraints, (TAPSOFT 89, Advanced Seminar on Foundations of Innovative Software Development. TAPSOFT 89, Advanced Seminar on Foundations of Innovative Software Development, Lecture Notes in Computer Science, 351 (1989)), 19-27
[22] Lassez, J.-L.; McAloon, K., A constraint sequent calculus, LICS, 52-61 (1990)
[23] Maher, M., A logic semantics for a class of committed choice languages, (Proceedings of ICLP4 (1987), MIT Press)
[24] Nelson, G., (Ph.D. Dissertation (1982), Stanford University)
[25] Rockafellar, R. T., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton · Zbl 0229.90020
[26] Saraswat, V., Concurrent constraint logic programming, (Ph.D. Dissertation (1989), Carnegie Mellon University) · Zbl 1002.68026
[27] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley · Zbl 0665.90063
[28] Shostak, R. E., On the SUP-INF method for proving Presburger formulas, JACM, 24, 529-543 (1977) · Zbl 0423.68052
[29] Steele, G.; Sussman, G., CONSTRAINTS-a Constraint Based Programming Language, AI Journal (1982)
[31] van Hentenryck, P., Constraint Satisfaction in Logic Programming (1989), MIT Press
[32] Weispfenning, V., Special issue on Algorithms in Real Algebraic Geometry, J. Symbolic Computation, 5, 1-274 (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.