Explanation-based weighted degree

dc.contributor.authorHebrard, Emmanuel
dc.contributor.authorSiala, Mohamed
dc.contributor.editorSalvagnin, Domenico
dc.contributor.editorLombardi, Michele
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2018-01-15T12:18:06Z
dc.date.available2018-01-15T12:18:06Z
dc.date.issued2017-05-31
dc.date.updated2018-01-12T12:25:21Z
dc.description.abstractThe 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.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationHebrard, 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_13en
dc.identifier.doi10.1007/978-3-319-59776-8_13
dc.identifier.endpage175en
dc.identifier.isbn978-3-319-59776-8
dc.identifier.journaltitleLecture Notes in Computer Sciencen
dc.identifier.startpage167en
dc.identifier.urihttps://hdl.handle.net/10468/5276
dc.identifier.volume10335en
dc.language.isoenen
dc.publisherSpringer International Publishingen
dc.relation.ispartofIntegration 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.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
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_13en
dc.subjectConstraint programmingen
dc.subjectWeighted degree heuristicen
dc.subjectGlobal constraintsen
dc.subjectComputer programmingen
dc.subjectConstraint theoryen
dc.subjectHeuristic programmingen
dc.subjectOperations researchen
dc.subjectGlobal constraintsen
dc.subjectITS efficienciesen
dc.subjectLinear inequalitiesen
dc.subjectState of the arten
dc.subjectVariable orderen
dc.subjectWeighted degreeen
dc.subjectWeighted degree heuristicen
dc.subjectHeuristic methodsen
dc.titleExplanation-based weighted degreeen
dc.typeBook chapteren
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
4580.pdf
Size:
466.25 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description: