Explanation-based weighted degree
dc.contributor.author | Hebrard, Emmanuel | |
dc.contributor.author | Siala, Mohamed | |
dc.contributor.editor | Salvagnin, Domenico | |
dc.contributor.editor | Lombardi, Michele | |
dc.contributor.funder | Science Foundation Ireland | en |
dc.date.accessioned | 2018-01-15T12:18:06Z | |
dc.date.available | 2018-01-15T12:18:06Z | |
dc.date.issued | 2017-05-31 | |
dc.date.updated | 2018-01-12T12:25:21Z | |
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.description.status | Peer reviewed | en |
dc.description.version | Accepted Version | en |
dc.format.mimetype | application/pdf | en |
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.doi | 10.1007/978-3-319-59776-8_13 | |
dc.identifier.endpage | 175 | en |
dc.identifier.isbn | 978-3-319-59776-8 | |
dc.identifier.journaltitle | Lecture Notes in Computer Scienc | en |
dc.identifier.startpage | 167 | en |
dc.identifier.uri | https://hdl.handle.net/10468/5276 | |
dc.identifier.volume | 10335 | 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.relation.project | info: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_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 |