Explanation-based weighted degree

Show simple item record

dc.contributor.author Hebrard, Emmanuel
dc.contributor.author Siala, Mohamed
dc.contributor.editor Salvagnin, Domenico
dc.contributor.editor Lombardi, Michele
dc.date.accessioned 2018-01-15T12:18:06Z
dc.date.available 2018-01-15T12:18:06Z
dc.date.issued 2017-05-31
dc.identifier.citation Hebrard, E. and Siala, M. (2017) 'Explanation-Based Weighted Degree', in Salvagnin, D. and Lombardi, M. (eds.) Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Lecture Notes in Computer Science, LCNS vol. 10335, Cham: Springer International Publishing, pp. 167-175. doi:10.1007/978-3-319-59776-8_13 en
dc.identifier.volume 10335 en
dc.identifier.startpage 167 en
dc.identifier.endpage 175 en
dc.identifier.isbn 978-3-319-59776-8
dc.identifier.uri http://hdl.handle.net/10468/5276
dc.identifier.doi 10.1007/978-3-319-59776-8_13
dc.description.abstract The weighted degree heuristic is among the state of the art generic variable ordering strategies in constraint programming. However, it was often observed that when using large arity constraints, its efficiency deteriorates significantly since it loses its ability to discriminate variables. A possible answer to this drawback is to weight a conflict set rather than the entire scope of a failed constraint. We implemented this method for three common global constraints (AllDifferent, Linear Inequality and Element) and evaluate it on instances from the MiniZinc Challenge. We observe that even with simple explanations, this method outperforms the standard Weighted Degree heuristic. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer International Publishing en
dc.relation.ispartof Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings. Part of the Lecture Notes in Computer Science book series (LNCS, volume 10335)
dc.rights © Springer International Publishing AG 2017. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-59776-8_13 en
dc.subject Constraint programming en
dc.subject Weighted degree heuristic en
dc.subject Global constraints en
dc.subject Computer programming en
dc.subject Constraint theory en
dc.subject Heuristic programming en
dc.subject Operations research en
dc.subject Global constraints en
dc.subject ITS efficiencies en
dc.subject Linear inequalities en
dc.subject State of the art en
dc.subject Variable order en
dc.subject Weighted degree en
dc.subject Weighted degree heuristic en
dc.subject Heuristic methods en
dc.title Explanation-based weighted degree en
dc.type Book chapter en
dc.type Conference item en
dc.internal.authorcontactother Mohamed Siala, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: mohamed.siala@insight-centre.org 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 2018-05-31
dc.date.updated 2018-01-12T12:25:21Z
dc.description.version Accepted Version en
dc.internal.rssid 421497205
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Lecture Notes in Computer Scienc en
dc.internal.copyrightchecked No !!CORA!! en
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Padua, Italy en
dc.internal.placepublication Cham en
dc.internal.IRISemailaddress mohamed.siala@insight-centre.org en
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