×

The octagon abstract domain for continuous constraints. (English) Zbl 1338.90393

The paper by Marie Pelleau, Charlotte Truchet and Frédéric Benhamou is a valuable contribution to the interface between convex analysis, geometry as being needed for programming, and continuous and combinatorial optimization, all of them being important areas in modern Operational Research (OR), economics, medicine and engineering, etc. This article is a rigorous study, based on which more general future research may be established and real-world applications can be made. Infinitely constrained problems, nonlinear problems and “robust” problems could just be three important subclasses to be mentioned here.
In fact, domains in continuous constraint programming are generally represented with the help of intervals whose \(n\)-ary Cartesian product (so-called box) are approximating the solution space. In this paper, the authors generalize that representation and suggest a generic solver where other domains representations can be employed. In this frame, they define a new representation for continuous domains through octagons. They generalize local consistency and “split” to that octagon representation. Experimental results display promising improvements of the performance, when addressing several classical benchmark problems.
This excellent article is well-structured, mathematically deep, well exemplified and illustrated, and carefully written.
The eight sections of this work are as follows: 1. Introduction, 2. Preliminaries, 3. Abstract domains for constraints, 4. Octagons, 5. Octagonal solving, 6. Experiments, 7. Related works, and 8. Conclusions.
Further analytic and numerical refinements and extensions, strong results and methods may be expected in the scientific community, inspired by this research article. These may take place in terms of Nonlinear Optimization, Convexification techniques, Semi-Infinite Optimization, Infinite Optimization, Optimal Control, Robust Optimization, Ridge Regression and Tikhonov Regularization, Pattern Recognition, Shape Detection, Tomography, Classification and Game Theory.
Such a future progress might support achievements in science and technology, finance and economics, computational biology, neuroscience and medicine.

MSC:

90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Apt, K.R. (1999). The essence of constraint propagation. Theoretical Computer Science, 221. · Zbl 0930.68164
[2] Araya, I., Trombettoni, G., Neveu, B. (2010). Exploiting monotonicity in interval constraint propagation. In Proceedings of the 24th AAAI conference on artificial intelligence. AAAI. · Zbl 1203.65086
[3] Benhamou, F. (1996). Heterogeneous constraint solvings. In Proceedings of the 5th international conference on algebraic and logic programming (pp. 62-76). · Zbl 1355.68030
[4] Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.F. (1999). Revisiting hull and box consistency. In Proceedings of the 16th international conference on logic programming (pp. 230-244).
[5] Chabert, G., & Jaulin, L. (2009). Contractor programming. Artificial Intelligence, 173, 1079-1100. · Zbl 1191.68628 · doi:10.1016/j.artint.2009.03.002
[6] Chen, L., Miné, A., Wang, J., Cousot, P. (2009). Interval polyhedra: An abstract domain to infer interval linear relationships. In Proceedings of the 16th international static analysis symposium (SAS’09) (pp. 309-325). · Zbl 1248.68140
[7] Cousot, P., & Cousot, R. (1976). Static determination of dynamic properties of programs. In Proceedings of the 2nd international symposium on programming (pp. 106-130). · Zbl 0393.68080
[8] Dechter, R., Meiri, I., Pearl, J. (1989). Temporal constraint networks. In Proceedings of the first international conference on principles of knowledge representation and reasoning. · Zbl 0709.68101
[9] Floyd, R. (1962). Algorithm 97: shortest path. Communications of the ACM, 5(6).
[10] Goldberg, D. (1991). What every computer scientist should know about floating point arithmetic. ACM Computing Surveys, 23(1), 5-48. · doi:10.1145/103162.103163
[11] Goldsztejn, A., & Granvilliers, L. (2010). A new framework for sharp and efficient resolution of ncsp with manifolds of solutions. Constraints, 15(2), 190-212. · Zbl 1203.65086 · doi:10.1007/s10601-009-9082-3
[12] Menasche. M., & Berthomieu, B. (1983). Time petri nets for analyzing and verifying time dependent communication protocols. In Protocol specification, testing, and verification.
[13] Miné, A. (2004). Domaines numériques abstraits faiblement relationnels. Ph.D. thesis, École Normale Supérieure.
[14] Miné, A. (2006). The octagon abstract domain. Higher-Order and Symbolic Computation, 19(1), 31-100. · Zbl 1105.68069 · doi:10.1007/s10990-006-8609-1
[15] Régin, J.C., & Rueher, M. (2005). Inequality-sum : a global constraint capturing the objective function: RAIRO Operations Research. · Zbl 1104.90051
[16] Rossi, F., van Beek, P., Walsh, T. (2006). Handbook of constraint programming (Foundations of Artificial Intelligence). Elsevier. · Zbl 1175.90011
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.