Online learning of variable ordering heuristics for constraint optimisation problems

Abstract

Solvers for constraint optimisation problems exploit variable and value ordering heuristics. Numerous expert-designed heuristics exist, while recent research learns novel, customised heuristics from past problem instances. This article addresses unseen problems for which no historical data is available. We propose one-shot learning of customised, problem instance-specific heuristics. To do so, we introduce the concept of deep heuristics, a data-driven approach to learn extended versions of a given variable ordering heuristic online. First, for a problem instance, an initial online probing phase collects data, from which a deep heuristic function is learned. The learned heuristics can look ahead arbitrarily-many levels in the search tree instead of a ‘shallow’ localised lookahead of classical heuristics. A restart-based search strategy allows for multiple learned models to be acquired and exploited in the solver’s optimisation. We demonstrate deep variable ordering heuristics based on the smallest, anti first-fail, and maximum regret heuristics. Results on instances from the MiniZinc benchmark suite show that deep heuristics solve 20% more problem instances while improving on overall runtime for the Open Stacks and Evilshop benchmark problems.