Constraint Logic Programming with Polynomial Constraints over Finite Domains

• Autorzy: Bergenti F. , Monica S. , Rossi G.

Identyfikatory

DOI

10.3233/FI-2018-1693

• Konferencja: Italian Conference on Computational Logic (Convegno Italiano di Logica Computazionale, CILC 2016) (31; 20-22.07.2016; Università degli Studi di Milano-Bicocca, Italy)
• Języki publikacji: EN

Abstrakty

EN

This paper introduces an instantiation of the constraint logic programming scheme called CLP(PolyFD) in which variables take values from finite subsets of the integers and constraints are expressed as equalities, inequalities, and disequalities of polynomials with integer coefficients. Such constraints, which we call polynomial constraints over finite domains, can be treated effectively by means of a specific solver under the assumption that initial approximations of the domains of variables are available. The proposed solver deals with constraints in a canonical form and it uses the modified Bernstein form of polynomials to detect the satisfiability of constraints. The solver is complete and a preliminary assessment of its performance is reported.

Słowa kluczowe

EN

constraint logic programming; modified Bernstein form; polynomial constraints over finite domains

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 161, nr 1/2
• Strony: 9--27
• Opis fizyczny: Bibliogr. 25 poz., rys., tab.

Twórcy

autor

Bergenti F.

• Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università degli Studi di Parma, Parco Area delle Scienze 53/A, 43124 Parma, Italy

autor

Monica S.

• Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università degli Studi di Parma, Parco Area delle Scienze 53/A, 43124 Parma, Italy

autor

Rossi G.

• Dipartimento di Scienze Matematiche, Fisiche e Informatiche, Università degli Studi di Parma, Parco Area delle Scienze 53/A, 43124 Parma, Italy

Bibliografia

• [1] Borralleras C, Lucas S, Oliveras A, Rodríguez-Carbonell E, Rubio A. SAT modulo linear arithmetic for solving polynomial constraints. Journal of Automated Reasoning, 2010. 48(1):107-131. URL http://hdl.handle.net/10251/37666.
• [2] von zur Gathen J, Gerhard J. Modern Computer Algebra. Cambridge University Press, Cambridge, UK, 2003. ISBN: 0521826462.
• [3] Steffens KG. The History of Approximation Theory: From Euler to Bernstein. Birkhäuser, Boston, MA, 2006. ISBN: 0-8176-4353-2.
• [4] Patil BV, Nataraj PSV, Bhartiya S. Global optimization of mixed-integer nonlinear (polynomial) programming problems: The Bernstein polynomial approach. Computing, 2012. 94(2):325-343.
• [5] Grimstad B, Sandnes A. Global optimization with spline constraints: A new branch-and-bound method based on B-splines. Journal of Global Optimization, 2016. 65(3):401-439. doi:10.1007/s10898-015-0358-4.
• [6] Jaffar J, Maher MJ. Constraint logic programming: A survey. Journal of Logic Programming, 1994. 19/20:503-581. URL https://doi.org/10.1016/0743-1066(94)90033-7.
• [7] Apt K. Principles of Constraint Programming. Cambridge University Press, Cambridge, UK, 2003. ISBN-10: 0521825830, 13: 978-0521825832.
• [8] Bergenti F, Monica S, Rossi G. Polynomial constraint solving over finite domains with the modified Bernstein form. In: Fiorentini C, Momigliano A (eds.), Procs. 31st Italian Conference on Computational Logic, volume 1645 of CEUR Workshop Proceedings. RWTH Aachen, 2016 pp. 118-131.
• [9] Bergenti F, Monica S, Rossi G. A subdivision approach to the solution of polynomial constraints over finite domains using the modified Bernstein form. In: Adorni G, Cagnoni S, Gori M, Maratea M (eds.), AI*IA 2016 Advances in Artificial Intelligence, volume 10037 of Lecture Notes in Computer Science. Springer International Publishing, 2016 pp. 179-191. doi:10.1007/978-3-319-49130-1_14.
• [10] Bergenti F, Monica S. Hyper-arc consistency of polynomial constraints over finite domains using the modified Bernstein form. Annals of Mathematics and Artificial Intelligence, 2017. 80(2):131-151. doi:10.1007/s10472-017-9544-z.
• [11] Bernstein SN. Démonstration du théorème de Weierstrass fondée sur le calcul des probabilités. Communications de la Société Mathématique de Kharkov, 1912. 2:XIII(1):1-2.
• [12] Lorentz GG. Bernstein Polynomials. University of Toronto Press, Toronto, ON, 1953.
• [13] Farouki RT. The Bernstein polynomial basis: A centennial retrospective. Computer Aided Geometric Design, 2012. 29(6):379-419. URL https://doi.org/10.1016/j.cagd.2012.03.001.
• [14] Garloff J, Smith AP. Solution of systems of polynomial equations by using Bernstein expansion. In: Alefeld G, Rohn J, Rump S, Yamamoto T (eds.), Symbolic Algebraic Methods and Verification Methods. Springer International Publishing, 2001 pp. 87-97. doi:10.1007/978-3-7091-6280-4_9.
• [15] Sánchez-Reyes J. Algebraic manipulation in the Bernstein form made simple via convolutions. Computer-Aided Design, 2003. 35:959-967. doi:10.1016/S0010-4485(03)00021-6.
• [16] Nataraj PSV, Arounassalame M. A new subdivision algorithm for the Bernstein polynomial approach to global optimization. International Journal of Automation and Computing, 2007. 4(4):342-352. doi:10.1007/s11633-007-0342-7.
• [17] Mourrain B, Pavone JP. Subdivision methods for solving polynomial equations. Journal of Symbolic Computation, 2009. 44(3):292-306. URL https://doi.org/10.1016/j.jsc.2008.04.016.
• [18] Ray S, Nataraj P. An efficient algorithm for range computation of polynomials using the Bernstein form. Journal of Global Optimization, 2009. 45:403-426. doi:10.1007/s10898-008-9382-y.
• [19] Farouki RT, Rajan VT. Algorithms for polynomials in Bernstein form. Computer-Aided Geometric Design, 1988. 5(1):1-26. URL https://doi.org/10.1016/0167-8396(88)90016-7.
• [20] Rossi F, van Beek P, Walsh T. Handbook of Constraint Programming. Elsevier, New York, NY, 2006. ISBN: 9780444527264, 9780080463803.
• [21] Smith AP. Fast construction of constant bound functions for sparse polynomials. Journal of Global Optimization, 2009. 43(2-3):445-458. doi:10.1007/s10898-007-9195-4.
• [22] Triska M. The finite domain constraint solver of SWI-Prolog. In: Schrijvers T, Thiemann P (eds.), Functional and Logic Programming, volume 7294 of Lecture Notes in Computer Science. Springer International Publishing, 2012 pp. 307-316. doi:10.1007/978-3-642-29822-6_24.
• [23] Wielemaker J, Schrijvers T, Triska M, Lager T. SWI-Prolog. Theory and Practice of Logic Programming, 2012. 12(1-2):67-96. URL https://doi.org/10.1017/S1471068411000494.
• [24] Garloff J. Convergent bounds for the range of multivariate polynomials. In: Nickel K (ed.), Interval Mathematics 1985, volume 212 of Lecture Notes in Computer Science. Springer International Publishing, 1986 pp. 37-56. http://www-home.htwg-konstanz.de/~garloff/ConvergentBounds.pdf.
• [25] Garloff J. The Bernstein algorithm. Interval Computations, 1993. 2:154-168. https://interval.louisiana.edu/reliable-computing-journal/1993/interval-computations-1993-2-pp-154-168.pdf.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).