×

zbMATH — the first resource for mathematics

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, (), 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
[7] Dickman, M. A. Model Theory and Real Algebraic Geometry. North Holland (to appear). · Zbl 0994.82058
[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] Fourier, J.B.J.; Kohler, D.A., Translation of a report by Fourier on his work on linear inequalities, Histoire de l’acadimie royale des sciences de 1’institut de France, 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, ()
[14] Jafar, J.; Michaylov, S., Methodology and implementation of a CLP system, ()
[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.; Khachiyan, L.G., Polynomial algorithms in linear programming, Doklady akademii nauk SSSR, 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, ()
[19] Lassez, J.-L.; Maher, M.; Marriott, K., Unification revisited, () · Zbl 0645.68046
[20] Lassez, J.L.; McAloon, K., Applications of a canonical form for generalized linear constraints, (), 703-710
[21] Lassez, J.-L.; McAloon, K., Independence of negative constraints, (), 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, ()
[24] Nelson, G., ()
[25] Rockafellar, R.T., Convex analysis, (1970), Princeton University Press Princeton · Zbl 0229.90020
[26] Saraswat, V., Concurrent constraint logic programming, () · 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)
[30] Ueda, K. Guarded Horn Clauses. MIT Press (to appear). · Zbl 0771.68037
[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.