Deepification: Learning Variable Ordering Heuristics in Constraint Optimization Problems

Deepification: Learning Variable Ordering Heuristics in Constraint Optimization Problems

Doolaard, F.P. (TU Delft Electrical Engineering, Mathematics and Computer Science)

Yorke-Smith, N. (mentor)
de Weerdt, M.M. (graduation committee)
Pouwelse, J.A. (graduation committee)

Delft University of Technology

Computer Science

2020-08-26

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.

Machine Learning
Constraint Programming
Combinatorial Optimization
Heuristic

http://resolver.tudelft.nl/uuid:fbab3fe2-e077-4d41-ace4-e434c25ce27f

Student theses

master thesis

© 2020 F.P. Doolaard