Deepification: Learning Variable Ordering Heuristics in Constraint Optimization Problems

Abstract

Constraint programming is a paradigm for solving combinatorial problems by checking whether constraints are satisfied in a constraint satisfaction problem or by optimizing an objective in a constraint optimization problem. To find solutions, the solver needs to find a variable and value ordering. Numerous heuristics designed by human experts already exist to guide search and recent research uses machine learning to learn new heuristics. In this work the concept of deep heuristics is introduced. First, data is collected during a probing phase after which a deep heuristic function is learned based on the smallest, anti first-fail, and maximum regret heuristics. The learned deep heuristics look arbitrarily many levels in a search tree instead of a single instant lookup for normal heuristics. The results show that deep heuristics solve 20.5% more problem instances than normal heuristics while improving on overall runtime for the Open Stacks and Evilshop problems.