Modelling Dynamic Programming-based global constraints in Constraint Programming

Show simple item record

dc.contributor.author Visentin, Andrea
dc.contributor.author Prestwich, Steven D.
dc.contributor.author Rossi, Roberto
dc.contributor.author Tarim, S. Armagan
dc.contributor.editor Le Thi, Hoai An
dc.contributor.editor Le, Hoai Minh
dc.contributor.editor Pham Dinh, Tao
dc.date.accessioned 2019-07-18T11:55:47Z
dc.date.available 2019-07-18T11:55:47Z
dc.date.issued 2019-06-15
dc.identifier.citation Visentin, A., Prestwich, S. D., Rossi, R. and Tarim, A. (2019) 'Modelling Dynamic Programming-based global constraints in Constraint Programming', in Le Thi, H., Le, H. and Pham Dinh, T. (eds) Optimization of Complex Systems: Theory, Models, Algorithms and Applications. World Congress on Global Optimization 2019. Advances in Intelligent Systems and Computing, vol. 991, pp. 417-427. doi: 10.1007/978-3-030-21803-4_42 en
dc.identifier.volume 991 en
dc.identifier.startpage 417 en
dc.identifier.endpage 427 en
dc.identifier.isbn 978-3-030-21802-7
dc.identifier.isbn 978-3-030-21803-4
dc.identifier.uri http://hdl.handle.net/10468/8201
dc.identifier.doi 10.1007/978-3-030-21803-4_42 en
dc.description.abstract Dynamic Programming (DP) can solve many complex problems in polynomial or pseudo-polynomial time, and it is widely used in Constraint Programming (CP) to implement powerful global constraints. Implementing such constraints is a nontrivial task beyond the capability of most CP users, who must rely on their CP solver to provide an appropriate global constraint library. This also limits the usefulness of generic CP languages, some or all of whose solvers might not provide the required constraints. A technique was recently introduced for directly modelling DP in CP, which provides a way around this problem. However, no comparison of the technique with other approaches was made, and it was missing a clear formalisation. In this paper we formalise the approach and compare it with existing techniques on MiniZinc benchmark problems, including the flow formulation of DP in Integer Programming. We further show how it can be improved by state reduction methods. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer Nature Switzerland AG en
dc.relation.ispartof World Congress on Global Optimization 2019
dc.relation.ispartof Le Thi, H., Le, H. and Pham Dinh, T. (eds) Optimization of Complex Systems: Theory, Models, Algorithms and Applications
dc.relation.uri https://wcgo2019.event.univ-lorraine.fr/
dc.rights © 2019, Springer Nature Switzerland AG. This is a post-peer-review, pre-copyedit version of a paper published in Le Thi H., Le H., Pham Dinh T. (eds) Optimization of Complex Systems: Theory, Models, Algorithms and Applications. WCGO 2019. Advances in Intelligent Systems and Computing, vol. 991. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-21803-4_42 en
dc.subject Constraint programming en
dc.subject Dynamic programming en
dc.subject MIP en
dc.subject Encoding en
dc.title Modelling Dynamic Programming-based global constraints in Constraint Programming en
dc.type Conference item en
dc.internal.authorcontactother Steven David Prestwich, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: s.prestwich@cs.ucc.ie en
dc.internal.availability Full text available en
dc.check.info Access to this article is restricted until 12 months after publication by request of the publisher. en
dc.check.date 2020-06-15
dc.date.updated 2019-07-18T11:31:12Z
dc.description.version Accepted Version en
dc.internal.rssid 493288136
dc.contributor.funder Science Foundation Ireland en
dc.contributor.funder European Regional Development Fund en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Advances in Intelligent Systems and Computing en
dc.internal.copyrightchecked Yes
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Metz, France en
dc.internal.IRISemailaddress s.prestwich@cs.ucc.ie en
dc.internal.IRISemailaddress andrea.visentin@insight-centre.org en
dc.internal.IRISemailaddress armagan.tarim@ucc.ie
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ en


Files in this item

This item appears in the following Collection(s)

Show simple item record

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement