Online Learning of Deeper Variable Ordering Heuristics for Constraint Optimisation Problems

F.P. Doolaard, N. Yorke-Smith

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

28 Downloads (Pure)

Abstract

Solvers for constraint optimisation problems exploit variable and value ordering heuristics. Numerous expert-designed heuristics exist, while recent research uses machine learning to learn novel heuristics. We introduce the concept of deep heuristics, a data-driven approach to learn extended versions of a given variable ordering heuristic. We demonstrate deep variable ordering heuristics based on the smallest, anti first-fail, and maximum regret heuristics. The results show that deep heuristics solve 20% more problem instances than classical ‘shallow’ heuristics.
Original languageEnglish
Title of host publicationBNAIC/BeneLearn 2021
Subtitle of host publication33rd Benelux Conference on Artificial Intelligence and 30th Belgian-Dutch Conference on Machine Learning
EditorsEdit Luis A. Leiva, Cédric Pruski, Réka Markovich, Amro Najjar, Christoph Schommer
Pages789-791
Publication statusPublished - 2021
Event33rd Benelux Conference on Artificial Intelligence and
30th Belgian-Dutch Conference on Machine Learning
- Esch-sur-Alzette, Luxembourg
Duration: 10 Nov 202112 Nov 2021

Conference

Conference33rd Benelux Conference on Artificial Intelligence and
30th Belgian-Dutch Conference on Machine Learning
Abbreviated titleBNAIC/BeneLearn 2021
Country/TerritoryLuxembourg
CityEsch-sur-Alzette
Period10/11/2112/11/21

Fingerprint

Dive into the research topics of 'Online Learning of Deeper Variable Ordering Heuristics for Constraint Optimisation Problems'. Together they form a unique fingerprint.

Cite this