Modelling Dynamic Programming-based global constraints in Constraint Programming
| 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.contributor.funder | Science Foundation Ireland | en |
| dc.contributor.funder | European Regional Development Fund | en |
| dc.date.accessioned | 2019-07-18T11:55:47Z | |
| dc.date.available | 2019-07-18T11:55:47Z | |
| dc.date.issued | 2019-06-15 | |
| dc.date.updated | 2019-07-18T11:31:12Z | |
| 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.description.status | Peer reviewed | en |
| dc.description.version | Accepted Version | en |
| dc.format.mimetype | application/pdf | en |
| 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.doi | 10.1007/978-3-030-21803-4_42 | en |
| dc.identifier.endpage | 427 | en |
| dc.identifier.isbn | 978-3-030-21802-7 | |
| dc.identifier.isbn | 978-3-030-21803-4 | |
| dc.identifier.journaltitle | Advances in Intelligent Systems and Computing | en |
| dc.identifier.startpage | 417 | en |
| dc.identifier.uri | https://hdl.handle.net/10468/8201 | |
| dc.identifier.volume | 991 | 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.project | info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ | en |
| 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 |
